APPLE TREE-POJ 3321
树上树状数组，lef记录次节点的编号，rig记录他的字节点中编号最大的，则sum(rig)-sum(lef-1)即为
所求值，此题会卡vector常数（我也不知道是什么东西）
#include<iostream> #include<string.h> #include<cmath> #include<vector> #define maxn 100000+10 using namespace std; int n,m,lef[maxn],rig[maxn],sum[maxn],tot,s[maxn]; vector<vector<int> > q(maxn); void add(int x,int d) { while(x<=n) { sum[x]+=d; x+=x&(-x); } } int susm(int x) { int ans=0; while(x) { ans+=sum[x]; x-=x&(-x); } return ans; } void dfs(int x) { lef[x]=tot; for(int i=0;i<q[x].size();i++) { tot++; dfs(q[x][i]); } rig[x]=tot; } int main() { while(cin>>n) { memset(sum,0,sizeof(sum)); memset(lef,0,sizeof(lef)); memset(rig,0,sizeof(rig)); memset(s,0,sizeof(s)); for(int i=0;i<maxn;i++) q[i].clear(); for(int i=1;i<=n-1;i++) { int x,y; cin>>x>>y; q[x].push_back(y); } tot=1; dfs(1); for(int i=1;i<=n;i++) { s[i]=1; add(i,1); } cin>>m; while(m--) { char s1[5]; int x; scanf("%s%d",s1,&x); if(s1[0]=='Q') { //int x; //cin>>x; cout<<susm(rig[x])-susm(lef[x]-1)<<endl; } else { //int x; //cin>>x; if(s[x]) add(lef[x],-1); else add(lef[x],1); s[x]=!s[x]; } } } return 0; }
Disharmony Trees HDU - 3015
树状数组加数据离散化，用三次排序解决即可
#include<iostream> #include<algorithm> using namespace std; #define maxn (int)1e5+5 #include<cstring> typedef long long ll; int lowbit(int x) { return x&(-x); } ll n,c[maxn],c1[maxn]; //c tong ji he zhi c1 tong ji ge shu struct node { ll x,h; }tree[maxn]; bool cmp(node a,node b) { return a.x<b.x; } bool cmp1(node a,node b) { return a.h<b.h; } void add(ll x,ll num,ll *s) { while(x<=n) { s[x]+=num; x+=lowbit(x); } } ll sum(ll x,ll *s) { ll ans=0; while(x) { ans+=s[x]; x-=lowbit(x); } return ans; } int main() { while(cin>>n) { for(int i=1;i<=n;i++) cin>>tree[i].x>>tree[i].h; sort(tree+1,tree+1+n,cmp); int ji=tree[1].x; tree[1].x=1; for(int i=2;i<=n;i++) { if(tree[i].x==ji) tree[i].x=tree[i-1].x; else { ji=tree[i].x; tree[i].x=i; } } int jilu=tree[n].x; sort(tree+1,tree+1+n,cmp1); ji=tree[1].h; tree[1].h=1; for(int i=2;i<=n;i++) { if(tree[i].h==ji) tree[i].h=tree[i-1].h; else { ji=tree[i].h; tree[i].h=i; } } sort(tree+1,tree+1+n,cmp1); memset(c,0,sizeof(c)); memset(c1,0,sizeof(c1)); for(int i=1;i<=n;i++) { add(tree[i].x,tree[i].x,c); add(tree[i].x,1,c1); } int xiao,da; ll ans=0; for(int i=1;i<=n;i++) { xiao=sum(tree[i].x-1,c1)*tree[i].x-sum(tree[i].x-1,c); da=(sum(jilu,c)-sum(tree[i].x,c))-(sum(jilu,c1)-sum(tree[i].x,c1))*tree[i].x; ans+=tree[i].h*(xiao+da); add(tree[i].x,-tree[i].x,c); add(tree[i].x,-1,c1); } cout<<ans<<endl; } return 0; }