A. Dove 打扑克
显然的结论是：超过$sqrt n$的牌堆不会超过$sqrt n$个。
所以可以分块维护信息：
对于牌数小于$sqrt n$的，用一个桶维护。
对于牌数大于$sqrt n$的，用$vector$暴力插入删除维护。
同时维护答案，为了做到$O(1)$修改，也用分块进行维护。
B. Cicada 与排序
值不同的数，位置一定是固定的。
所以可以只对值相同的数在类似归并的过程中进行$dp$。
考虑每一个值，设$dp_{i,j,dep}$表示这个值在原序列上出现的第$i$个副本，在归并排序深度为$dep$的意义下排名为$j$的概率。
处理出数组$g_{i,j}$表示归并排序过程中，两个指针分别指向$i,j$的概率，
$f_{i,j}$表示第$i$位转移到第$j$位的概率，可以在递推$g$数组的同时简单求出。
然后随便转移就完了。
C. Cicada 拿衣服
考虑题中给出的限制$min+or-max-and$。
不妨分别提出其中的$min-max,or-and$。
可以枚举当前考虑的右端点。
那么对于不同的左端点：
$or-and$只有$2*log max(a_i)$种不同的取值，
因为二进制位分别对应只增不减，只减不增。
$min-max$随着左端点不断减小单调递减。
那么可以枚举每一个不同的取值，这个可以用链表简单维护（其实用两个数组暴力重构就可以）。
二分求出符合要求的最靠左的位置就可以。
然而这样做的复杂度是$O(nlog^2n)$的，其实有一些无用的状态。
因为之要求最靠左的左端点，从左到右枚举左端点所在的区间，在第一个可行区间二分更新答案后结束枚举就完了。
为了二分时$O(1)$查询，可以使用ST表维护。
然而刚刚学到了新的数据结构猫树，而且还可以和$zkw$线段树一起用，所以打起来就很帅。
1 #include<iostream> 2 #include<cstdio> 3 #define lch p<<1 4 #define rch p<<1|1 5 using namespace std; 6 const int N=1e6+50007; 7 struct node{ 8 int pos,And,Or; 9 }sa[105],sb[105]; 10 int n,k,bit,ca,cb; 11 int a[N],mx[22][N],mn[22][N],lg[N],ans[N<<1]; 12 void build(int p,int l,int r,int dep){ 13 if(l==r) return ; 14 int mid=l+r>>1; 15 build(lch,l,mid,dep+1); 16 build(rch,mid+1,r,dep+1); 17 mx[dep][mid]=mn[dep][mid]=a[mid]; 18 mx[dep][mid+1]=mn[dep][mid+1]=a[mid+1]; 19 for(int i=mid-1;i>=l;--i) mn[dep][i]=min(mn[dep][i+1],a[i]),mx[dep][i]=max(mx[dep][i+1],a[i]); 20 for(int i=mid+2;i<=r;++i) mn[dep][i]=min(mn[dep][i-1],a[i]),mx[dep][i]=max(mx[dep][i-1],a[i]); 21 } 22 void dfs(int p,int l,int r,int Ans){ 23 Ans=max(Ans,ans[p]); 24 if(l==r){ 25 if(l>1&&l<=n+1) printf("%d ",Ans); 26 return ; 27 } 28 int mid=l+r>>1; 29 dfs(lch,l,mid,Ans); 30 dfs(rch,mid+1,r,Ans); 31 } 32 inline int query_min(int l,int r){ 33 if(l==r) return a[l]; 34 int k=lg[bit]-lg[(l-1)^(r-1)]; 35 return min(mn[k][l],mn[k][r]); 36 } 37 inline int query_max(int l,int r){ 38 if(l==r) return a[l]; 39 int k=lg[bit]-lg[(l-1)^(r-1)]; 40 return max(mx[k][l],mx[k][r]); 41 } 42 inline void modify(int l,int r,int val){ 43 for(l+=bit-1,r+=bit+1;l^r^1;l>>=1,r>>=1){ 44 if(~l&1) ans[l^1]=max(ans[l^1],val); 45 if(r&1) ans[r^1]=max(ans[r^1],val); 46 } 47 } 48 inline int read(register int x=0,register char ch=getchar(),register int f=0){ 49 for(;!isdigit(ch);ch=getchar()) f=ch=='-'; 50 for(; isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48); 51 return f?-x:x; 52 } 53 int main(){ 54 n=read(); k=read(); 55 for(int i=1;i<=n;++i) a[i]=read(); 56 for(bit=1;bit<=n+1;bit<<=1); 57 for(int i=1;i<=bit;++i) lg[i]=lg[i>>1]+1; 58 for(int i=1;i<=bit+n;++i) ans[i]=-1; 59 build(1,1,bit,1); 60 for(int i=1;i<=n;++i){ 61 for(int j=1;j<=ca;++j) sa[j].And&=a[i],sa[j].Or|=a[i]; 62 sa[++ca]=(node){i,a[i],a[i]}; cb=0; 63 for(int j=1;j<=ca;++j) if(j==ca||sa[j].And!=sa[j+1].And||sa[j].Or!=sa[j+1].Or) sb[++cb]=sa[j]; 64 for(int j=1;j<=cb;++j) sa[j]=sb[j]; 65 ca=cb; 66 int flag=0; 67 for(int j=1;j<=ca&&!flag;++j) 68 if(sa[j].Or-sa[j].And+query_min(sa[j].pos,i)-query_max(sa[j].pos,i)>=k){ 69 int l=sa[j-1].pos+1,r=sa[j].pos; 70 while(l<r){ 71 int mid=l+r>>1; 72 if(sa[j].Or-sa[j].And+query_min(mid,i)-query_max(mid,i)>=k) r=mid; 73 else l=mid+1; 74 } 75 modify(l,i,i-l+1); 76 flag=1; 77 } 78 } 79 dfs(1,1,bit,-1); 80 return 0; 81 }