考场
开考感觉 T3 比较可做。T1 看上去不难但毫无思路。
先想了 25min T3，想到一个确定左端点，二分最长的右端点，甚至想到了用猫树维护区间 or and。。。上厕所回来发现假了，没有单调性
T1 还是不会做，T2 甚至不会写暴力。直到 8.10 才结束思考。
T1 暴力有 80pts，先写了
继续看 T3，根据区间变大后四个变量的变化情况想到了分治，又是想了很久发现复杂度假了，心态就炸了。这时候已经 9.20 了，洗了把脸强行冷静，写了 T3 暴力，但状态很差，写错很多细节。
最后 30min 看 T2，感觉可以枚举 rnd() 的值来算出每种情况下的位置，觉得不太好写在归并排序，预处理了的个数组假装它是随机数。但预处理多长却不好确定。一开始是 \(n\)，但样例都过不去，瞎胡分析一波感觉是每个数值的元素个数减一的和，也不太对。最终预处理的 \(21\) 位。
res
rk10 80+15+28
T2 后面的点都 T 了，开到 \(20\) 能多拿 20pts
rk1 熊子豪 100+0+92
rk2 yzf 80+0+100
rk3 肖鸣孜 80+100+0
总结
sol
双没时间写了
T1
const int N = 1e5+5;
int n,m;
int mx,fa[N],val[N],cnt[N];
vector<int> vec;
int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }
void add(int i)
{ if( !cnt[i]++ ) vec.insert(lower_bound(vec.begin(),vec.end(),i),i); }
void del(int i)
{ if( !--cnt[i] ) vec.erase(remove(vec.begin(),vec.end(),i)); }
signed main() {
read(n,m);
For(i,1,n) fa[i] = i, val[i] = 1, add(1);
while( m-- ) {
int op,x,y; read(op);
if( op == 1 ) {
read(x,y); x = find(x), y = find(y);
if( x == y ) continue;
del(val[x]), del(val[y]);
fa[y] = x, val[x] += val[y];
add(val[x]);
} else {
read(x);
LL ans = 0, suf = 0;
if( !x ) {
for(int i : vec) ans += cnt[i] * (cnt[i]-1ll) / 2;
++x;
}
for(auto it = vec.begin(); it != vec.end(); ++it) suf += cnt[*it];
for(auto itl = vec.begin(), itr = itl; itr != vec.end(); ++itl) {
while( itr != vec.end() && *itr-*itl < x ) suf -= cnt[*itr++];
if( itr == vec.end() ) break;
ans += cnt[*itl] * suf;
}
write(ans);
}
}
return iocl();
}
T2
我写了另一种 DP，时间复杂度也是 \(O(n^3)\)，但不知道为什么比 sol做法 跑得慢多了
const int N = 505, mod = 998244353, inv2 = 499122177;
int n,a[N];
LL f[N][N][N],g[N][N];
void merge(int u,int l,int r) {
if( l == r ) return f[u][l][l] = 1, void();
int mid = l+r>>1;
merge(u+1,l,mid), merge(u+1,mid+1,r);
memset(g,0,sizeof g);
g[l][mid+1] = 1;
For(i,l,mid+1) For(j,mid+1,r+1) if( i <= mid || j <= r ) {
g[i][j] %= mod;
if( j == r+1 ) g[i+1][j] += g[i][j];
else if( i == mid+1 ) g[i][j+1] += g[i][j];
else if( a[i] < a[j] ) g[i+1][j] += g[i][j];
else if( a[i] > a[j] ) g[i][j+1] += g[i][j];
else g[i+1][j] += g[i][j] * inv2 %mod, g[i][j+1] += g[i][j] * inv2 %mod;
}
For(i,l,r) For(j,l,mid+1) For(k,mid+1,r+1) if( j <= mid || k <= r ) {
if( k == r+1 ) f[u][i][j+k-mid-1] += f[u+1][i][j] * g[j][k] %mod;
else if( j == mid+1 ) f[u][i][j+k-mid-1] += f[u+1][i][k] * g[j][k] %mod;
else if( a[j] < a[k] ) f[u][i][j+k-mid-1] += f[u+1][i][j] * g[j][k] %mod;
else if( a[j] > a[k] ) f[u][i][j+k-mid-1] += f[u+1][i][k] * g[j][k] %mod;
else f[u][i][j+k-mid-1] += (f[u+1][i][j]+f[u+1][i][k]) * g[j][k] %mod * inv2 %mod;
}
For(i,l,r) For(j,l,r) f[u][i][j] %= mod;
sort(a+l,a+r+1);
}
signed main() {
read(n);
For(i,1,n) read(a[i]);
merge(1,1,n);
For(i,1,n) {
LL ans = 0;
For(j,1,n) ans += f[1][i][j] * j %mod;
write(ans%mod,' ');
}
return iocl();
}
T3
const int N = 1e6+5;
int n,m,a[N];
struct Node { int r,o,an; int val() { return o-an; } };
list<Node> lis;
namespace st {
int lg[N],f[20][N],g[20][N];
void init() {
For(i,2,n) lg[i] = lg[i>>1] + 1;
For(i,1,n) f[0][i] = g[0][i] = a[i];
For(j,1,19) for(int i = 1; i+(1<<j)-1 <= n; ++i)
f[j][i] = max(f[j-1][i],f[j-1][i+(1<<j-1)]),
g[j][i] = min(g[j-1][i],g[j-1][i+(1<<j-1)]);
}
int mx(int l,int r) { int k = lg[r-l+1]; return max(f[k][l],f[k][r-(1<<k)+1]); }
int mn(int l,int r) { int k = lg[r-l+1]; return min(g[k][l],g[k][r-(1<<k)+1]); }
}
namespace seg {
#define ls (u<<1)
#define rs (u<<1|1)
struct Node { int l,r,mx; } t[N*4];
void build(int u,int l,int r) {
t[u].l = l, t[u].r = r, t[u].mx = -1;
if( l == r ) return;
int mid = l+r>>1;
build(ls,l,mid), build(rs,mid+1,r);
}
void modify(int u,int l,int r) {
if( l <= t[u].l && t[u].r <= r ) { ckmax(t[u].mx,r-l+1); return; }
if( l <= t[ls].r ) modify(ls,l,r);
if( t[rs].l <= r ) modify(rs,l,r);
}
void print(int u) {
if( t[u].l == t[u].r ) { write(t[u].mx,' '); return; }
ckmax(t[ls].mx,t[u].mx), ckmax(t[rs].mx,t[u].mx);
print(ls), print(rs);
}
#undef ls
#undef rs
}
bool check(list<Node>::iterator it,int l,int r)
{ return it->val()+st::mn(l,r)-st::mx(l,r) >= m; }
signed main() {
read(n,m);
For(i,1,n) read(a[i]);
st::init(), seg::build(1,1,n);
For(i,1,n) {
for(auto it = lis.begin(); it != lis.end(); ++it)
it->o |= a[i], it->an &= a[i];
lis.pb(Node{i,a[i],a[i]});
for(auto itl = lis.begin(), itr = itl; ++itr != lis.end(); )
if( itl->val() == itr->val() ) lis.erase(itl), itl = itr;
else ++itl;
for(auto it = lis.begin(); it != lis.end(); ++it) if( check(it,it->r,i) ) {
int l = 1, r = it->r;
if( it != lis.begin() ) l = (--it)->r+1, ++it;
while( l < r ) {
int mid = l+r>>1;
if( check(it,mid,i) ) r = mid;
else l = mid+1;
}
seg::modify(1,l,i);
break;
}
}
seg::print(1);
return iocl();
}