传送门
我只想知道为什么这题的弱化版会出现在我们今天的%你赛里……
题意：给你一堆操作$(l,r)$，表示将区间$(l,r)$按升序排序。以及$q$个询问，每次询问一个数列能否在上述操作之后变为有序
首先，我们要知道如果只有一次询问的话，我们要怎么乱搞。首先，排序的交换次数下界等于逆序对个数，我们只要对于$(l,r)$中的每一个满足$a[i]>a[i+1]$的元素，交换$i$和$i+1$，那么交换次数就能刚好为逆序对个数，即$O(n^2)$
所以对于每一个操作，我们都可以在区间中消逆序对。考虑怎么快速找到所有的逆序对。我们可以把所有的满足$a[i]>a[i+1]$的$i$给丢进set里，那么每次只要二分找到在这个区间中的$i$，然后交换，删掉原来的逆序对并加入新的逆序对就可以了。时间复杂度为$O((n^2+m)logn)$，优于$O(nmlogn)$代码如下
void SORT(rint l,rint r){ rint i; while((i=*s.upper_bound(l-1))>=l&&i<r){ s.erase(i),swap(a[i],a[i+1]); if(a[i]<a[i+2]&&a[i+1]>a[i+2])s.insert(i+1); if(a[i-1]>a[i]&&a[i-1]<a[i+1])s.insert(i-1); } }
然后就是神仙操作了……我们先考虑什么样的初始序列可以被排好序，我们从$01$序列开始考虑，如果一个$111000$的初始序列可以通过一堆操作之后变得有序，那么$101010$的序列必然也可以（感性理解一下发现很显然），那么我们就说$101010$比$111000$更优。总的来说，一个序列中$0$越靠左，$1$越靠右，那么这个序列越接近升序，这个序列就越优。设$pos(a,i)$表示数列$a$中第$i$个$1$所在的位置。对于两个数列来说，如果$a$比$b$更优，当且仅当对于所有$i$都有$pos(a,i)geq pos(b,i)$。
那么我们只要能得到最差的能被排好序的初始序列，那么所有比它更优的一定能够排好序。
于是我们可以设原数列为$A$，且是一个$n$的排列（如果不是的话我们可以把它给离散，并把元素相同的按下表排列，可以发现这样并不会影响结果）。考虑如何从$01$序列拓展到这个$n$排列，对于$A$和某个数值$k$，定义$01$序列$B_k$，$B_k[i]$为$1$当且仅当$A[i]geq k$。
于是我们发现，如果对于所有的$k=2,3,...n$，$B_k$都能在这些操作下变得有序，那么原排列也可以
直接做太慢了，我们设原排列为$1,2,...,n$，然后对于$m$次操作，我们按$i$从$m$到$1$的顺序每一次都用上面的方法使区间$[l_i,r_i]$降序排序（变为最差的）
最后得到的序列中，小于$k$的位置用$0$表示，其他位置用$1$表示，得到的$01$序列为$C_k$，且$C_k$只要更改一个位置上的值就能变为$C_{k-1}$
于是只要所有的$B_k$都比对应的$C_k$优秀，那么原排列就能在若干次操作后变为有序，即$B_k$的任意一个前缀和都不能大于$C_k$的前缀和
如果我们把$B_k$中的$1$取相反数，并把两个前缀和相加，那么只要每一个前缀和都大于等于$0$即可。设$posb[i]$表示元素$i$在$B_k$中的位置，$posc[i]$表示元素$i$在$C_k$中的位置。当求完$k=i$要求$k=i+1$的时候，$posb[i+1]$处的元素变为$-1$，那么它以及后面所有数的前缀和都会减一，$posc[i]$的变化同理。于是我们只要维护好前缀和，并判断最小的前缀和是否小于$0$即可。区间赋值和区间取$min$用线段树就可以了
1 //minamoto 2 #include<bits/stdc++.h> 3 #define rint register int 4 #define min(x,y) ((x)<(y)?(x):(y)) 5 #define ls (p<<1) 6 #define rs (p<<1|1) 7 #define ppd(p,v) (mn[p]+=(v),tag[p]+=(v)) 8 #define mem(a) (memset(a,0,sizeof(a))) 9 using namespace std; 10 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 11 char buf[1<<21],*p1=buf,*p2=buf; 12 int read(){ 13 int res,f=1;char ch; 14 while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); 15 for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); 16 return res; 17 } 18 const int N=2005,M=1e6+5; 19 int n,m,q,c[N],posc[N],b[N],posb[N],mn[N<<2],tag[N<<2]; 20 struct ques{int l,r;}p[M];set<int>s; 21 struct node{ 22 int val,id; 23 inline bool operator <(const node &b)const{return val==b.val?id<b.id:val<b.val;} 24 }f[N]; 25 void SORT(rint l,rint r){ 26 rint i; 27 while((i=*s.upper_bound(l-1))>=l&&i<r){ 28 s.erase(i),swap(c[i],c[i+1]); 29 if(c[i+1]<c[i+2]&&c[i]>c[i+2])s.insert(i+1); 30 if(c[i-1]<c[i]&&c[i-1]>c[i+1])s.insert(i-1); 31 } 32 } 33 inline void pd(int p){if(tag[p])ppd(ls,tag[p]),ppd(rs,tag[p]),tag[p]=0;} 34 void update(int p,int l,int r,int ql,int qr,int v){ 35 if(ql<=l&&qr>=r)return (void)(ppd(p,v)); 36 int mid=(l+r)>>1;pd(p); 37 if(ql<=mid)update(ls,l,mid,ql,qr,v); 38 if(qr>mid)update(rs,mid+1,r,ql,qr,v); 39 mn[p]=min(mn[ls],mn[rs]); 40 } 41 int main(){ 42 // freopen("testdata.in","r",stdin); 43 n=read(),m=read(),q=read(); 44 for(int i=1;i<=m;p[i].l=read(),p[i].r=read(),++i); 45 for(int i=1;i<=n;c[i]=i,++i); 46 for(int i=1;i<n;s.insert(i),++i); 47 for(int i=m;i;SORT(p[i].l,p[i].r),--i); 48 for(int i=1;i<=n;posc[c[i]]=i,++i); 49 while(q--){ 50 for(int i=1;i<=n;f[i].val=read(),f[i].id=i,++i); 51 sort(f+1,f+1+n); 52 for(int i=1;i<=n;b[f[i].id]=i,++i); 53 for(int i=1;i<=n;posb[b[i]]=i,++i); 54 mem(mn),mem(tag); 55 bool flag=1; 56 for(int i=2;i<=n;++i){ 57 update(1,1,n,posb[i-1],n,1); 58 update(1,1,n,posc[i-1],n,-1); 59 if(mn[1]<0){flag=0;break;} 60 } 61 puts(flag?"AC":"WA"); 62 } 63 return 0; 64 }