题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3295
题目--洛谷3157：https://www.luogu.org/problemnew/show/P3157
题目--洛谷3193：https://www.luogu.org/problemnew/show/P1393
1.树状数组套权值线段树
有点卡空间。线段树节点的*100怎么算？
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int N=1e5+5; int n,m,f[N],rt[N],tot,ps[N]; ll ans; struct Node{ int ls,rs,sum; }a[N*100]; int getsm(int x) { int ret=0;for(;x;x-=(x&-x))ret+=f[x];return ret; } void addsm(int x) { for(;x<=n;x+=(x&-x))f[x]++; } void insert(int &cr,int l,int r,int p,int fx) { if(!cr)cr=++tot;a[cr].sum+=fx; if(l==r)return; int mid=((l+r)>>1); if(p<=mid)insert(a[cr].ls,l,mid,p,fx); else insert(a[cr].rs,mid+1,r,p,fx); } void insert(int x,int v,int fx) { for(;x<=n;x+=(x&-x))insert(rt[x],1,n,v,fx); } int query(int cr,int l,int r,int x) { if(r<=x)return a[cr].sum; int mid=((l+r)>>1); if(x<=mid)return query(a[cr].ls,l,mid,x); return a[a[cr].ls].sum+query(a[cr].rs,mid+1,r,x); } int query(int x,int v) { int ret=0;for(;x;x-=(x&-x))ret+=query(rt[x],1,n,v);return ret; } int pre(int p,int x) { return query(p,n)-query(p,x); } int suf(int p,int x) { return query(n,x)-query(p,x); } int main() { scanf("%d%d",&n,&m);int x; for(int i=1;i<=n;i++) { scanf("%d",&x);ans+=getsm(n)-getsm(x); addsm(x);insert(i,x,1);ps[x]=i; } for(int i=1;i<=m;i++) { printf("%lld ",ans);scanf("%d",&x); ans-=pre(ps[x],x)+suf(ps[x],x); insert(ps[x],x,-1); } return 0; }
加上离散化就能过洛谷3193了。通过数喜+1。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=4e4+5; int n,m,f[N],rt[N],tot,vl[N]; ll ans,tp[N],t[N]; struct Node{ int ls,rs,sum; }a[N*100]; int getsm(int x) { int ret=0;for(;x;x-=(x&-x))ret+=f[x];return ret; } void addsm(int x) { for(;x<=n;x+=(x&-x))f[x]++; } void insert(int &cr,int l,int r,int p,int fx) { if(!cr)cr=++tot;a[cr].sum+=fx; if(l==r)return; int mid=((l+r)>>1); if(p<=mid)insert(a[cr].ls,l,mid,p,fx); else insert(a[cr].rs,mid+1,r,p,fx); } void insert(int x,int v,int fx) { for(;x<=n;x+=(x&-x))insert(rt[x],1,n,v,fx); } int query(int cr,int l,int r,int x) { if(r<=x)return a[cr].sum; int mid=((l+r)>>1); if(x<=mid)return query(a[cr].ls,l,mid,x); return a[a[cr].ls].sum+query(a[cr].rs,mid+1,r,x); } int query(int x,int v) { int ret=0;for(;x;x-=(x&-x))ret+=query(rt[x],1,n,v);return ret; } int pre(int p,int x) { return query(p,n)-query(p,x); } int suf(int p,int x) { return query(n,x)-query(p,x); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&t[i]),tp[i]=t[i]; sort(tp+1,tp+n+1);int cnt=unique(tp+1,tp+n+1)-tp-1; for(int i=1;i<=n;i++)vl[i]=lower_bound(tp+1,tp+cnt+1,t[i])-tp; for(int i=1;i<=n;i++) { ans+=getsm(n)-getsm(vl[i]); addsm(vl[i]);insert(i,vl[i],1); } printf("%lld ",ans);int x; for(int i=1;i<=m;i++) { scanf("%d",&x); ans-=pre(x,vl[x])+suf(x,vl[x]); insert(x,vl[x],-1);printf("%lld ",ans); } return 0; }
2.CDQ分治
学习TJ。https://www.cnblogs.com/candy99/p/6440745.html
1)先按位置排序，再按时间分治。
2)把影响加到树状数组里。往下递归之前先撤销修改。
3)应该是空间n+m，时间 (n+m) * log(n) * log(n)。（一个log分治，一个log树状数组，(n+m)是每一层的操作次数）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=1e5+5,M=5e4+5; int n,m,tot,pos[N],f[N]; //树状数组是值 ll ans[M]; struct Cz{ int t,ps,v,id,type; Cz(int t=0,int p=0,int v=0,int i=0,int y=0):t(t),ps(p),v(v),id(i),type(y) {} bool operator<(const Cz k)const { return ps<k.ps; } }a[N+M],tp[N+M]; void add(int x,int v) { for(;x<=n;x+=(x&-x))f[x]+=v; } int query(int x) { int ret=0;for(;x;x-=(x&-x))ret+=f[x];return ret; } void CDQ(int l,int r) //l,r是时间,也已经是角标 { if(l==r)return; int mid=((l+r)>>1); for(int i=l;i<=r;i++) if(a[i].t<=mid)add(a[i].v,a[i].type); else ans[a[i].id]+=a[i].type*(query(n)-query(a[i].v)); //在我前面、比我大的 for(int i=l;i<=r;i++) if(a[i].t<=mid)add(a[i].v,-a[i].type); //撤销操作，不影响递归下去 for(int i=r;i>=l;i--) if(a[i].t<=mid)add(a[i].v,a[i].type); else ans[a[i].id]+=a[i].type*query(a[i].v-1); //在我后面、比我小的 for(int i=r;i>=l;i--) if(a[i].t<=mid) add(a[i].v,-a[i].type); //撤销操作 int p0=l,p1=mid+1; for(int i=l;i<=r;i++) if(a[i].t<=mid)tp[p0++]=a[i]; //去左边/右边，但没有改变相对位置。 else tp[p1++]=a[i]; //即一开始的按位置排序效果还在 for(int i=l;i<=r;i++)a[i]=tp[i]; CDQ(l,mid);CDQ(mid+1,r); } int main() { scanf("%d%d",&n,&m);int x; for(int i=1;i<=n;i++) { scanf("%d",&x);pos[x]=i; a[++tot]=Cz(tot,i,x,0,1); } for(int i=1;i<=m;i++) { scanf("%d",&x); a[++tot]=Cz(tot,pos[x],x,i,-1); } sort(a+1,a+tot+1); CDQ(1,tot); for(int i=0;i<m;i++)printf("%lld ",ans[i]),ans[i+1]+=ans[i]; //ans求出来的其实是每个操作引起的变化量 return 0; //(它不是一直在*type么) }