POJ 3067 Japan（树状数组 ）

题意：在东边有n座城市,从北到南编号依次为1,2,3.n 在西边有m座城市,从北到南编号分别为1,2,3.m 现要在南北城市之间修建k条超级高速公路,求会出现多少个十字路口

思路：找到合适的统计方法，先经过适当排序，再用RMQ解决

//2756 KB	469 ms	
#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; typedef long long ll; const int M = 1e6+100; int n,m,k; struct Way { int u,v; }es[M]; bool cmp(const Way&a,const Way&b) { if(a.u==b.u) return a.v>b.v; return a.u>b.u; } int sum[1010]; inline int lowbit(int x) { return x&-x; } int getsum(int rt) { int s=0; for(int i=rt;i>0;i-=lowbit(i)) s+=sum[i]; return s; } void update(int rt) { for(int i=rt;i<=1000;i+=lowbit(i)) { sum[i]++; } } int main() { int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { memset(sum,0,sizeof(sum)); scanf("%d%d%d",&n,&m,&k); for(int i=0;i