POJ3067 Japan 树状数组的应用 - c++编程基础

这题以前做过，用的线段树，现在用树状数组做一次，

题意：给你n个城市在日本左边，m个城市在日本右边，然后k条路，问你这k条路有几个交点，注意城市的序号其实就是一维坐标所在位置，所以就是两条平行的数轴，上面有点，而且之间有连线，问你有多少交点

一开始不好想把，这种题目也就排排序来试试看了，先对要修建的公路进行排序，然后再看这样是否可以更加方便的求出交点的数论，取路的左边点为先决条件从小到大排列，若相等则按照右边点来升序排列，然后以左边点为序号和value值为1进行插入树状数组，先求出当前已经插入树状数组中的点和当前的这个点有多少个交点，然后累加求和就是最后的答案了

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                  > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; const int n = 1000 + 5; int c[10000 + 5]; typedef struct Node { int l,r; }; Node node[1000000 + 5]; void clear() { memset(c,0,sizeof(c)); memset(node,0,sizeof(node)); } bool cmp(Node x,Node y) { return x.l < y.l || (x.l == y.l && x.r < y.r); } int lowbit(int x) { return x&(-x); } void add(int i,int value) { while(i <= n) { c[i] += value; i += lowbit(i); } } int get_sum(int i) { int sum = 0; while(i > 0) { sum += c[i]; i -= lowbit(i); } return sum ; } int main() { int t; int Case = 0; scanf("%d",&t); while(t--) { clear(); int n,m,k; scanf("%d %d %d",&n,&m,&k); int maxn = -1; for(int i=0;i