树状数组
题意是，在左右两边各有m和n个点的二分图中有k条边(xi,yi)，问这k条边之间两两相交了多少次（端点不算）。
首先读入每条边，然后按x由小到大排序，初始化ans=0，然后重复：
（1）将xi连续相同的一组边加入图中；
（2）对下一组中的每条边j，求与之前的边相交的次数，由于之前的边必有x<xj，因此求y>yj的边数即可。
最后输出ans即为答案。
其中的（1）和（2）可以用树状数组来实现：通过O(lgn)地修改、询问，可以使总时间复杂度达到O(klgn)。
树状数组的实现有个小技巧，x&-x可以O(1)地取到x最低位的1。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int t,m,n,el,ed[1000001]; long long ans; struct E { int w,e; bool operator < (const E &p) const { return w<p.w; } }e[1000000]; void init() { int i; ans=0; memset(ed,0,sizeof ed); for(i=0;i<el;i++) scanf("%d%d",&e[i].w,&e[i].e); sort(e,e+el); } void ins(int i) { while(i<=n) { ed[i]++; i+=i&-i; } } int que(int i) { int s=0; while(i) { s+=ed[i]; i-=i&-i; } return s; } void solve() { int i,j,k,l; for(i=0;i<el&&e[i].w==e[0].w;i++) ins(e[i].e); for(;i<el;i=j) { for(j=i;j<el&&e[j].w==e[i].w;j++) ans+=i-que(e[j].e); for(j=i;j<el&&e[j].w==e[i].w;j++) ins(e[j].e); } printf("Test case %d: %lld\n",++t,ans); } int main() { scanf("%*d"); while(~scanf("%d%d%d",&n,&m,&el)) { init(); solve(); } return 0; } |