bzoj2141: 排队

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2141 题解：据说是树套树，还没看题，待更。。。。。。。 　　感觉比较水，就一个线段树套平衡树就可以了吧，但是一节课才40分钟就简述一下方法吧，下午再写吧。。。。。 　　感觉也没什么好讲的耶，交换两个点（x，y），影响的只会是（x--y)这个区间，于是他们交换后对ans的贡献就是在（x，y）中 ans+=比x大的-比x小的+比y小的-比y大的（注意：x,y会重复），就可以了，于是用平衡树维护，感觉这种水题20分钟就够了，但我太垃圾（只是不想写，我去上体育课了。。。。。。。），膜拜cys，ls等神犇。。。。。。 啊，为什么会T？　　唉，第一次体验到常数太大的happy。。。。。。。。。。。。。。。。。。。。 线段树+平衡树： #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #define N 30000 #define M 120000 using namespace std; int ans,sz,n,m; int a[N]; int ls[M],rs[M],root[M],s[M],w[M],rnd[M],v[M]; int read() { int x=0; char ch; bool bo=0; while (ch=getchar(),ch<'0'||ch>'9') if (ch=='-') bo=1; while (x=x*10+ch-'0',ch=getchar(),ch>='0'&&ch<='9'); if (bo) return -x; return x; } void updata(int k){s[k]=s[ls[k]]+s[rs[k]]+w[k];} void rturn(int &k){int t=ls[k]; ls[k]=rs[t]; rs[t]=k; s[t]=s[k]; updata(k); k=t;} void lturn(int &k){int t=rs[k]; rs[k]=ls[t]; ls[t]=k; s[t]=s[k]; updata(k); k=t;} void insert(int &k,int val) { if(!k){k=++sz; s[k]=w[k]=1; v[k]=val; rnd[k]=rand();return;} s[k]++; if (v[k]==val) w[k]++; else if (val<v[k]) {insert(ls[k],val); if (rnd[ls[k]]<rnd[k]) rturn(k);} else if (val>v[k]) {insert(rs[k],val); if (rnd[rs[k]]<rnd[k]) lturn(k);} } void build(int k,int l,int r,int pos,int val) { insert(root[k],val); if (l==r) return ; int mid=(l+r)>>1; if (pos<=mid) build(k*2,l,mid,pos,val); else build(k*2+1,mid+1,r,pos,val); } void del(int &k,int num) { if (v[k]==num) { if (w[k]>1){w[k]--; s[k]--; return;} if (ls[k]*rs[k]==0) k=ls[k]+rs[k]; else if (rnd[ls[k]]<rnd[rs[k]]){rturn(k); del(k,num);} else {lturn(k); del(k,num);} } else if (v[k]>num) {del(ls[k],num); s[k]--;} else{del(rs[k],num); s[k]--;} } void change(int k,int l,int r,int pos,int pre,int now) { del(root[k],pre); insert(root[k],now); if (l==r) return; int mid=(l+r)>>1; if (pos<=mid) change(k*2,l,mid,pos,pre,now); else change(k*2+1,mid+1,r,pos,pre,now); } int ask_max(int k,int num) { if (!k) return 0; if (v[k]==num) return s[rs[k]]; else if (v[k]>num) return ask_max(ls[k],num)+rs[k]+w[k]; else if (v[k]<num) return ask_max(rs[k],num); } int ask_min(int k,int num) { if (!k) return 0; if (v[k]==num) return s[ls[k]]; else if (v[k]>num) return ask_min(ls[k],num); else return ask_min(rs[k],num)+ls[k]+w[k]; } int query_summax(int k,int l,int r,int x,int y,int num) { //cout<<k<<" "<<l<<" "<<r<<" "<<x<<" "<<" "<<y<<" "<<num<<endl; if (l==x && r==y) { //cout<<" "<<x<<" "<<y<<" "<<num<<endl; return ask_max(root[k],num); } int mid=(l+r)>>1; if (y<=mid) return query_summax(k*2,l,mid,x,y,num); else if (x>mid) return query_summax(k*2+1,mid+1,r,x,y,num); else { return (query_summax(k*2,l,mid,x,mid,num)+query_summax(k*2+1,mid+1,r,mid+1,y,num)); } } int query_summin(int k,int l,int r,int x,int y,int num) { if (l==x && r==y) return ask_min(root[k],num); int mid=(l+r)>>1; if (y<=mid) return query_summin(k*2,l,mid,x,y,num); else if (x>mid) return query_summin(k*2+1,mid+1,r,x,y,num); else { return (query_summin(k*2,l,mid,x,mid,num)+query_summin(k*2+1,mid+1,r,mid+1,y,num)); } } int main() { n=read(); for (int i=1; i<=n; i++) a[i]=read(); for (int i=1; i<=n; i++) build(1,1,n,i,a[i]); for (int i=1; i<=n; i++) ans+=query_summax(1,1,n,1,i,a[i]);//,cout<<ans<<endl; printf("%d\n",ans); //cout<<" "<<query_summax(1,1,3,2,3,140); m=read(); for (int i=1; i<=m; i++) { int x=read(),y=read(); ans+=+query_summax(1,1,n,x,y-1,a[x])-query_summin(1,1,n,x,y-1,a[x]); ans+=+query_summin(1,1,n,x+1,y,a[y])-query_summax(1,1,n,x+1,y,a[y]); if (a[x]<a[y]) ans++; else ans--; int t=a[x]; change(1,1,n,x,a[x],a[y]); a[x]=a[y]; change(1,1,n,y,a[y],t); a[y]=t; printf("%d\n",ans); } } View Code

唉，只能写常数小的分块+树状数组咯。。。。。Fuck ls holy shit

待更。。。。。。