竟然？竟然？竟然？
我已经用了半个键盘的编号了$\text{T_T}$
$\mathbb{AFO}$感稍强
h1是不是有点大？
ZJ+TJ：
T1
以为是什么数据结垢，但是是个链表。
所以可以使用 vector set list 维护。
复杂度的话，可证为$O(q \sqrt{N})$
在主定理里tui到点什么。
$\Theta$平均复杂度。
$O$最劣复杂度。
$\Omega$最优复杂度。
于是以后尽量用对。
那么就是这样拉。
首先我们的链表维护的是桶，因为总共只有$N$张牌，
于是$\sum\limits_{i=1}^{n}val_i = N$
那么最多只会有$\sqrt{N}$种取值。
为了使值尽量多，我们将数列$\{ 1,2,3,4,5,6,7,\cdots \}$的前$i$项放入$val$
于是由等差数列求和公式$\frac{k(k+1)}{2}$
得到最多时:
$$
\begin{align}
\frac{k(k+1)}{2} &=& N \\
k &=& \sqrt{N}
\end{align}
$$
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>//#include "debug.h"#define N 111111
#define M 333333
#define LL long longusing namespace std;int qn,cn;
int siz[M],pre[M],val[M];
set<int>cd;
int fa[M];inline int faind(int x){
if(fa[x]!=x)fa[x]=faind(fa[x]);
return fa[x];
}
void unite(int a,int b){
a=faind(a);
b=faind(b);
fa[a]=b;
siz[b]+=siz[a];
}
int main(){
int opt,a,b,c;
scanf("%d%d",&cn,&qn);
for(int i=1;i<=cn;i++){
fa[i]=i;
siz[i]=1;
}
val[1]=cn;cd.insert(1);
pre[1]=cn;
for(int __i=1;__i<=qn;__i++){
scanf("%d",&opt);
if(opt==1){
//pour(val,1,cn,3,"BVal");
//pour(cd,3,"BeforeI");
scanf("%d%d",&a,&b);
a=faind(a),b=faind(b);
if(a==b)continue;
int sa=siz[a],sb=siz[b],sab=siz[a]+siz[b];
unite(a,b);
val[sa]--;
if(val[sa]==0)cd.erase(sa);
val[sb]--;
if(val[sb]==0)cd.erase(sb);
val[sab]++;
cd.insert(sab);
pre[*cd.begin()]=val[*cd.begin()];
for(auto i=cd.begin();;i++){
auto j=i;j++;
if(j==cd.end())break;
pre[*j]=pre[*i]+val[*j];
}
//pour(val,1,cn,3,"AVal");
//pour(cd,3,"AfterI");
}
else{
//pour(val,1,cn,3,"Q");
//pour(cd,3,"Qcd");
scanf("%d",&c);
LL ans=0;
if(c!=0){
auto i=cd.end(),j=cd.end();
i--,j--;
//puts("VVVVVVVVVVVV");
//Out(*i);Out(c);
//puts("^^^^^^^^^^^^");
while(1){
while(i!=cd.begin() && (*j)-(*i)<c)
i--;
if((*j)-(*i)>=c)
ans+=pre[(*i)]*val[(*j)];
if(j==cd.begin())break;
j--;
}
}
else{
auto fi=cd.end();
fi--;
LL va=pre[*fi];
ans=va*(va-1)/2;
}
printf("%lld\n",ans);
}
}
}
T2，买个坑
T3
水果：
于是大声喊： cin 就是行！
卡常不想写快读，马上 cin 解绑直接上！
把 cin ， cout 从C风格缓存中解出来就跑飞快。
但是请注意，
cin 解绑后请不要同时使用 scanf 和 cin ，不然会重复读入。
cout 解绑后请不要同时使用 printf 和 cout ，不然可能会错序输出。
挂了不要来找我
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#define N 1111111using namespace std;const int Skyh=700;
int arr[N],pn,lim;
int ans[N];int main(){
cin.sync_with_stdio(false);
memset(ans,-1,sizeof ans);
cin>>pn>>lim;
for(int i=1;i<=pn;i++)
cin>>arr[i];
if(pn<=30000){
for(int i=1;i<=pn;i++){
int maxn=0,
minn=INT_MAX,
orn=0,
andn=INT_MAX,
red=i-1;
for(int j=i;j<=pn;j++){
maxn=max(maxn,arr[j]);
minn=min(minn,arr[j]);
orn |=arr[j];
andn&=arr[j];
int ykst=minn+orn-maxn-andn;
if(ykst>=lim)
red=j;
}
for(int j=i;j<=red;j++){
ans[j]=max(ans[j],red-i+1);
}
}
}
else{
for(int i=1;i<=pn;i++){
int maxn=0,
minn=INT_MAX,
orn=0,
andn=INT_MAX,
red=i-1;
int qj=min(pn,i+Skyh);
for(int j=i;j<=qj;j++){
maxn=max(maxn,arr[j]);
minn=min(minn,arr[j]);
orn |=arr[j];
andn&=arr[j];
int ykst=minn+orn-maxn-andn;
if(ykst>=lim)
red=j;
}
for(int j=i;j<=red;j++){
ans[j]=max(ans[j],red-i+1);
}
}
}
for(int i=1;i<=pn;i++)
printf("%d ",ans[i]);
puts("");
}
