<span>模拟91 题解</span>

显然的结论是：超过$\sqrt n$的牌堆不会超过$\sqrt n$个。

所以可以分块维护信息：

对于牌数小于$\sqrt n$的，用一个桶维护。

对于牌数大于$\sqrt n$的，用$vector$暴力插入删除维护。

同时维护答案，为了做到$O(1)$修改，也用分块进行维护。

值不同的数，位置一定是固定的。

所以可以只对值相同的数在类似归并的过程中进行$dp$。

考虑每一个值，设$dp_{i,j,dep}$表示这个值在原序列上出现的第$i$个副本，在归并排序深度为$dep$的意义下排名为$j$的概率。

处理出数组$g_{i,j}$表示归并排序过程中，两个指针分别指向$i,j$的概率，

$f_{i,j}$表示第$i$位转移到第$j$位的概率，可以在递推$g$数组的同时简单求出。

然后随便转移就完了。

考虑题中给出的限制$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 }