BZOJ - 2141 排队 (动态逆序对，区间线段树套权值线段树)

交换两个数的位置，只有位于两个数之间的部分会受到影响，因此只需要考虑两个数之间有多少数对a[l]和a[r]产生的贡献发生了变化即可。

感觉像是个带修改的二维偏序问题。(修改点$(x,y)$的值，维护和查询位于$(x_1,y_1)$与$(x_2,y_2)$之间的点的个数)

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=2e4+,inf=0x3f3f3f3f;

 int n,m,n2,rt[N<<],ls[N*],rs[N*],sum[N*],tot,a[N],b[N],ans;

 #define lson (u<<1)

 #define rson (u<<1|1)

 #define mid ((l+r)>>1)

 void upd2(int p,int x,int& u,int l=,int r=n2) {

     if(!u)u=++tot;

     sum[u]+=x;

     if(l==r)return;

     p<=mid?upd2(p,x,ls[u],l,mid):upd2(p,x,rs[u],mid+,r);

 }

 int qry2(int L,int R,int& u,int l=,int r=n2) {

     if(l>=L&&r<=R)return sum[u];

     if(l>R||r<L)return ;

     return qry2(L,R,ls[u],l,mid)+qry2(L,R,rs[u],mid+,r);

 }

 void upd(int p,int x,int dx,int u=,int l=,int r=n) {

     upd2(x,dx,rt[u]);

     if(l==r)return;

     p<=mid?upd(p,x,dx,lson,l,mid):upd(p,x,dx,rson,mid+,r);

 }

 int qry(int L,int R,int L2,int R2,int u=,int l=,int r=n) {

     if(l>=L&&r<=R)return qry2(L2,R2,rt[u]);

     if(l>R||r<L)return ;

     return qry(L,R,L2,R2,lson,l,mid)+qry(L,R,L2,R2,rson,mid+,r);

 }

 int main() {

     scanf("%d",&n);

     for(int i=; i<=n; ++i)scanf("%d",&a[i]);

     for(int i=; i<=n; ++i)b[i]=a[i];

     sort(b+,b++n),n2=unique(b+,b++n)-(b+);

     for(int i=; i<=n; ++i)a[i]=lower_bound(b+,b++n2,a[i])-b;

     for(int i=; i<=n; ++i)ans+=qry(,n,a[i]+,n2),upd(i,a[i],);

     printf("%d\n",ans);

     scanf("%d",&m);

     while(m--) {

         int l,r;

         scanf("%d%d",&l,&r);

         if(l>r)swap(l,r);

         if(l==r||a[l]==a[r]);

         else {

             if(a[l]<a[r])ans+=qry(l+,r-,a[l]+,a[r])+qry(l+,r-,a[l],a[r]-)+;

             else ans-=qry(l+,r-,a[r]+,a[l])+qry(l+,r-,a[r],a[l]-)+;

             upd(l,a[l],-),upd(l,a[r],);

             upd(r,a[r],-),upd(r,a[l],);

             swap(a[l],a[r]);

         }

         printf("%d\n",ans);

     }

     return ;

 }

还有理论上能够AC的线段树套treap的版本，可惜常数太大TLE了~QAQ~

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=2e4+,inf=0x3f3f3f3f;

 int n,m,n2,rt[N<<],ch[N*][],val[N*],siz[N*],rd[N*],tot,a[N],b[N],ans;

 #define lson (u<<1)

 #define rson (u<<1|1)

 #define mid ((l+r)>>1)

 void pu(int u) {siz[u]=siz[ch[u][]]+siz[ch[u][]]+;}

 int newnode(int x) {int u=++tot; ch[u][]=ch[u][]=,siz[u]=,val[u]=x,rd[u]=rand(); return u;}

 void rot(int& u,int f) {

     int v=ch[u][f];

     ch[u][f]=ch[v][f^],ch[v][f^]=u;

     pu(u),pu(v),u=v;

 }

 void ins(int& u,int x) {

     if(!u) {u=newnode(x); return;}

     int f=x>val[u];

     ins(ch[u][f],x);

     if(rd[ch[u][f]]>rd[u])rot(u,f);

     if(u)pu(u);

 }

 void del(int& u,int x) {

     if(!u)return;

     if(val[u]==x) {

         if(!ch[u][]||!ch[u][])u=ch[u][]|ch[u][];

         else {

             int f=rd[ch[u][]]>rd[ch[u][]];

             rot(u,f),del(ch[u][f^],x);

         }

     } else del(ch[u][x>val[u]],x);

     if(u)pu(u);

 }

 int lb(int u,int x) {

     int ret=;

     for(; u; u=ch[u][x>val[u]])if(val[u]>=x)ret=val[u];

     return ret;

 }

 int ub(int u,int x) {

     int ret=;

     for(; u; u=ch[u][x>=val[u]])if(val[u]>x)ret=val[u];

     return ret;

 }

 int rnk(int u,int x) {

     int ret=;

     for(; u; u=ch[u][x>val[u]])if(x>val[u])ret+=siz[ch[u][]]+;

     return ret+;

 }

 int sum(int u,int l,int r) {return l>r?:rnk(u,ub(u,r))-rnk(u,lb(u,l));}

 void upd(int p,int x,int dx,int u=,int l=,int r=n) {

     dx==?ins(rt[u],x):del(rt[u],x);

     if(l==r)return;

     p<=mid?upd(p,x,dx,lson,l,mid):upd(p,x,dx,rson,mid+,r);

 }

 int qry(int L,int R,int L2,int R2,int u=,int l=,int r=n) {

     if(l>=L&&r<=R)return sum(rt[u],L2,R2);

     if(l>R||r<L)return ;

     return qry(L,R,L2,R2,lson,l,mid)+qry(L,R,L2,R2,rson,mid+,r);

 }

 void build(int u=,int l=,int r=n) {

     ins(rt[u],~inf),ins(rt[u],inf);

     if(l==r)return;

     build(lson,l,mid),build(rson,mid+,r);

 }

 int main() {

     srand(time());

     scanf("%d",&n);

     for(int i=; i<=n; ++i)scanf("%d",&a[i]);

     for(int i=; i<=n; ++i)b[i]=a[i];

     sort(b+,b++n),n2=unique(b+,b++n)-(b+);

     for(int i=; i<=n; ++i)a[i]=lower_bound(b+,b++n2,a[i])-b;

     build();

     for(int i=; i<=n; ++i)ans+=qry(,n,a[i]+,n2),upd(i,a[i],);

     printf("%d\n",ans);

     scanf("%d",&m);

     while(m--) {

         int l,r;

         scanf("%d%d",&l,&r);

         if(l>r)swap(l,r);

         if(l==r||a[l]==a[r]);

         else {

             if(a[l]<a[r])ans+=qry(l+,r-,a[l]+,a[r])+qry(l+,r-,a[l],a[r]-)+;

             else ans-=qry(l+,r-,a[r]+,a[l])+qry(l+,r-,a[r],a[l]-)+;

             upd(l,a[l],-),upd(l,a[r],);

             upd(r,a[r],-),upd(r,a[l],);

             swap(a[l],a[r]);

         }

         printf("%d\n",ans);

     }

     return ;

 }

后续：我把treap的区间求和方式改了稍微改了一下，卡时过掉了~~

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=2e4+,inf=0x3f3f3f3f;

 int n,m,n2,rt[N<<],ch[N*][],val[N*],siz[N*],rd[N*],tot,a[N],b[N],ans;

 #define lson (u<<1)

 #define rson (u<<1|1)

 #define mid ((l+r)>>1)

 void pu(int u) {siz[u]=siz[ch[u][]]+siz[ch[u][]]+;}

 int newnode(int x) {int u=++tot; ch[u][]=ch[u][]=,siz[u]=,val[u]=x,rd[u]=rand(); return u;}

 void rot(int& u,int f) {

     int v=ch[u][f];

     ch[u][f]=ch[v][f^],ch[v][f^]=u;

     pu(u),pu(v),u=v;

 }

 void ins(int& u,int x) {

     if(!u) {u=newnode(x); return;}

     int f=x>val[u];

     ins(ch[u][f],x);

     if(rd[ch[u][f]]>rd[u])rot(u,f);

     if(u)pu(u);

 }

 void del(int& u,int x) {

     if(!u)return;

     if(val[u]==x) {

         if(!ch[u][]||!ch[u][])u=ch[u][]|ch[u][];

         else {

             int f=rd[ch[u][]]>rd[ch[u][]];

             rot(u,f),del(ch[u][f^],x);

         }

     } else del(ch[u][x>val[u]],x);

     if(u)pu(u);

 }

 int lb(int u,int x) {

     int ret=;

     for(; u; u=ch[u][x>val[u]])if(x>val[u])ret+=siz[ch[u][]]+;

     return ret;

 }

 int ub(int u,int x) {

     int ret=;

     for(; u; u=ch[u][x>=val[u]])if(x>=val[u])ret+=siz[ch[u][]]+;

     return ret;

 }

 int sum(int u,int l,int r) {return ub(u,r)-lb(u,l);}

 void upd(int p,int x,int dx,int u=,int l=,int r=n) {

     dx==?ins(rt[u],x):del(rt[u],x);

     if(l==r)return;

     p<=mid?upd(p,x,dx,lson,l,mid):upd(p,x,dx,rson,mid+,r);

 }

 int qry(int L,int R,int L2,int R2,int u=,int l=,int r=n) {

     if(l>=L&&r<=R)return sum(rt[u],L2,R2);

     if(l>R||r<L)return ;

     return qry(L,R,L2,R2,lson,l,mid)+qry(L,R,L2,R2,rson,mid+,r);

 }

 int main() {

     srand(time());

     scanf("%d",&n);

     for(int i=; i<=n; ++i)scanf("%d",&a[i]);

     for(int i=; i<=n; ++i)b[i]=a[i];

     sort(b+,b++n),n2=unique(b+,b++n)-(b+);

     for(int i=; i<=n; ++i)a[i]=lower_bound(b+,b++n2,a[i])-b;

     for(int i=; i<=n; ++i)ans+=qry(,n,a[i]+,n2),upd(i,a[i],);

     printf("%d\n",ans);

     scanf("%d",&m);

     while(m--) {

         int l,r;

         scanf("%d%d",&l,&r);

         if(l>r)swap(l,r);

         if(l==r||a[l]==a[r]);

         else {

             if(a[l]<a[r])ans+=qry(l+,r-,a[l]+,a[r])+qry(l+,r-,a[l],a[r]-)+;

             else ans-=qry(l+,r-,a[r]+,a[l])+qry(l+,r-,a[r],a[l]-)+;

             upd(l,a[l],-),upd(l,a[r],);

             upd(r,a[r],-),upd(r,a[l],);

             swap(a[l],a[r]);

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

BZOJ - 2141 排队 (动态逆序对，区间线段树套权值线段树)

最新文章

热门文章