[树组BIT]训练两题重新理解ver.
|
树状数组重（jiao）新（wo）理（zuo）解（ren） POJ-2352 加加加都给我加 输入是一行一行按照x从小到大给出的，所以对于每个点，要考虑的只是x比它小的点的个数。即记录各个x的情况，并且对于一个特定的x要把它前面的x求和。 噔噔噔，树状数组可以较优地实现改点、求和（而且好写）。 cin无法承受这么大的输入并t了，关同步也不行，只能用scanf
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int ma = 32003; int n; int x,y; int ans[ma],a[ma]; int lb(int k) { return k & (-k); } int q(int x) { int ans = 0; for (int i = x; i > 0; i -= lb(i))ans += a[i]; return ans; } void add(int x) { for (int i = x; i < ma; i += lb(i))a[i]++; } int main() { cin >> n; for(int i=0;i<n;i++) { scanf("%d%d",&x,&y); x++; ans[q(x)]++; add(x); } for (int i = 0; i < n; i++)cout << ans[i] << endl; return 0; } 对了，我发现不删掉system（“pause”）交上去也可以，诶嘿 ++x是因为题目给的x是可以等于零的，而如果add（0）就会爆炸 先查后加，查询当前点之前符合条件的点的个数，然后使这个level的点的数量++，并把当前点加入x套餐（不是
POJ-3067 逆序数对&逆序对数&逆序数@[email?protected] 只有背板子能力的红小豆在发现线段树/树状数组和逆序对数有关系的时候整颗豆都是懵的 原理：将数与其位置对应，按照数的大小将位置sort，接着求当前位置前有几个位置数是比当前位置数小，再用i减去个数，得到比当前位置数大的位置数的个数，即逆序对数。 e.g. 数：1 4 3 2 位置：1 2 3 4 sort 数：1 2 3 4? 位置数：1 4 3 2 以树状数组作为实现，即利用query求和，再用add把一系列树组+1
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int t,n,m,k; int l[1000005],r[1000005],nu[1000005]; int a[1005]; bool cmp(int i,int j) { if (l[i] == l[j])return r[i] < r[j]; return l[i] < l[j]; } int lb(int k) { return k & (-k); } int q(int x) { int ans = 0; for (int i = x; i > 0; i -= lb(i))ans += a[i]; return ans; } void add(int x) { for (int i = x; i < 1005; i+=lb(i))a[i]++; } int main() { cin >> t; int co = 0; while (t--) { ++co; memset(a,0,sizeof(a)); cin >> n >> m >> k; for (int i = 1; i <= k; i++) { scanf("%d%d",&l[i],&r[i]); nu[i] = i; } sort(nu + 1,nu + 1 + k,cmp); long long ans = 0; for (int i = 1; i <= k; i++) { ans += i - q(r[nu[i]])-1; add(r[nu[i]]); } cout << "Test case " << co << ": " << ans << endl; } return 0; } 对了，要纠正一件事，memset还是比单纯for要快一些的。 神仙用pair存的左右序号，毕竟它自带先按first从小到大再按second来sort 蒟蒻想起了间接排序法就这么实行了，除了括号有点多，好像没什么问题 因为从又从1开始了，所以ans+=i-...-1 ? 什么时候。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
