什么你说你不知道 NANAN 是哪里，那一定是南岸啦
不膜拜360小广告，它今天发挥不稳定。
T1
什么你怎么知道我的假算法跑过去了。
理论上可是高达 O(10^9) 的！
回归正题，由于我们只在乎每一个数存在的数码(digit)，因此我们可以用一个小于 2^{10} 的数来表示某个数码存不存在的状态（是的这其实勉强算状压），然后把这玩意丢进桶里。
暴力枚举 0 \leq i \leq j<1023，如果 i \& j 不为 0，那么答案加上 cnt_i \times cnt_j，注意若 i=j 时需要除二。
时间复杂度 O(n+m^2)，其中 m=1023。
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<11)+5;
typedef long long LL;
int n,cnt[N];
LL res=0;
void divide(LL x)
{
int S=0;
while(x)
{
S|=(1<<(x%10));
x/=10;
}
cnt[S]++;
}
int main()
{
freopen("training.in","r",stdin);
freopen("training.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
LL x;
scanf("%lld",&x);
divide(x);
}
for(int i=0;i<N;i++)
{
for(int j=i;j<N;j++)
{
if(i&j&&cnt[i]&&cnt[j])
{
if(i==j)res+=(1LL*cnt[i]*(cnt[i]-1)/2);
else res+=1LL*cnt[i]*cnt[j];
}
}
}
printf("%lld",res);
return 0;
}
T2
什么你怎么知道题解类似拓扑排序结果跑超时了。
什么你怎么知道我和题解思路一样
首先二分答案，在判断函数中首先将度数 <mid 的点加入队列，像拓扑排序一样操作，如果最后没有剩下任何一个点，那么就不合法。
具体细节（没有细节）见代码，时间复杂度 O((n+m)\log n)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5;
typedef long long LL;
int n,m,st[N],q[N],d[N],td[N];
vector<int>G[N];
int check(int deg)
{
int hh=0,tt=-1,cnt=0;
for(int i=1;i<=n;i++)
{
td[i]=d[i];
st[i]=0;
if(td[i]<deg)
{
q[++tt]=i;
st[i]=1;
cnt++;
}
}
while(hh<=tt)
{
int u=q[hh++];
for(int j:G[u])
{
if(!st[j]&&(--td[j])<deg)
{
q[++tt]=j;
st[j]=1;
cnt++;
}
}
}
return cnt<n;
}
int main()
{
freopen("end.in","r",stdin);
freopen("end.out","w",stdout);
scanf("%d%d",&n,&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
d[a]++,d[b]++;
}
int l=0,r=n;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
printf("%d",l);
return 0;
}
T3
什么你怎么知道我大样例1跑了40s
什么你怎么知道改题时候由于电脑死机后还原我这题重写了两遍
首先要先考虑将询问离线，否则很容易往启发式合并的方向越想越远。（确实）
对于操作一，先建出树型结构（具体地，如果两个树之前未曾合并，那么新开一个点作为他们的父亲）
然后对于建出的树，跑一遍DFS，预处理出求LCA所需要的一些数组。
然后就可以愉悦的处理询问了。
对于操作一，开 map<pair,int> 维护
对于操作二，将其记录在根部。
对于操作三，答案是 map 里的加上LCA~根的路径和。
显然树上差分（使用树状数组）就可以了
时间复杂度 O(m \log n)，注意可能实现时需要开启二倍空间。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=6e5+5;
typedef pair<int,int>PII;
struct node
{
int op,x,y;
}Q[N];
vector<int>G[M];
map<PII,int>res;
int n,m,cnt,tr[M],par[M],Size[M];
int d[M],fa[M][27],id[M],timestamp;
int find(int x)
{
if(par[x]==x)return x;
else return par[x]=find(par[x]);
}
void dfs(int u,int father)
{
Size[u]=1;
d[u]=d[father]+1;
fa[u][0]=father;
id[u]=++timestamp;
for(int j=1;j<=25;j++)fa[u][j]=fa[fa[u][j-1]][j-1];
for(int j:G[u])
{
if(j==father)continue;
dfs(j,u);
Size[u]+=Size[j];
}
}
int LCA(int a,int b)
{
if(d[a]<d[b])swap(a,b);
for(int i=25;~i;i--)
{
if(d[fa[a][i]]>=d[b])a=fa[a][i];
}
if(a==b)return a;
for(int i=25;~i;i--)
{
if(fa[a][i]!=fa[b][i])
{
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
int lowbit(int x){return x&(-x);}
void modify(int x,int v){for(;x<=cnt;x+=lowbit(x))tr[x]+=v;}
int query(int x)
{
int res=0;
for(;x;x-=lowbit(x))res+=tr[x];
return res;
}
int main()
{
freopen("everyone.in","r",stdin);
freopen("everyone.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n+m;i++)par[i]=i;
cnt=n;
for(int i=1;i<=m;i++)
{
int op,x,y;
scanf("%d%d",&op,&x);
if(op==1||op==3)scanf("%d",&y);
Q[i]={op,x,y};
if(op==1)
{
x=find(x),y=find(y);
if(x!=y)
{
par[x]=par[y]=++cnt;
G[cnt].push_back(x);
G[cnt].push_back(y);
}
}
}
for(int i=1;i<=cnt;i++)
{
if(par[i]==i)dfs(i,0);
par[i]=i;
}
for(int i=1;i<=m;i++)
{
int op=Q[i].op,x=Q[i].x,y=Q[i].y;
if(op==1)
{
res[{x,y}]++;
res[{y,x}]++;
x=find(x),y=find(y);
if(x!=y)par[x]=par[y]=++n;
}
else if(op==2)
{
x=find(x);
//printf("%d-!%d\n",x,id[x]);
modify(id[x],1);
modify(id[x]+Size[x],-1);
}
else
{
int lca=LCA(x,y);
if(find(x)!=find(y))puts("0");
else printf("%d\n",query(id[lca])+res[{x,y}]);
}
}
return 0;
}
T4
LXL 老师还是忘不掉他的数据结构！
于是这题扫描线。
对于询问区间与覆盖区间，全部按左端点排序后倒着处理。
这样保证了左端点一定不会溢出，只需考虑右端点。
设 f_i 表示 i 被覆盖所需要的区间最小右端点，如果不存在则设为 +\infty
满足 [l,r] 有解的充分必要条件是 \forall i \in [l,r],f_i \leq r.
于是可以通过线段树（带懒标记，维护区间最大值）维护。
时间复杂度 O(n \log n)，只要线段树不写错写起来很快。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,INF=1e9;
int n,m,q,res[N];
struct segment
{
int l,r,id;
}M[N],Q[N];
int cmp(segment a,segment b){return a.l>b.l;}
struct node
{
int l,r,w,tag;
}tr[N<<2];
void pushup(int u){tr[u].w=max(tr[u<<1].w,tr[u<<1|1].w);}
void pushdown(int u)
{
if(tr[u].tag==INF)return;
tr[u<<1].w=min(tr[u<<1].w,tr[u].tag);
tr[u<<1|1].w=min(tr[u<<1|1].w,tr[u].tag);
tr[u<<1].tag=min(tr[u<<1].tag,tr[u].tag);
tr[u<<1|1].tag=min(tr[u<<1|1].tag,tr[u].tag);
tr[u].tag=INF;
}
void build(int u,int l,int r)
{
tr[u]={l,r,INF,INF};
if(l==r)return;
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int x)
{
if(l<=tr[u].l&&tr[u].r<=r)
{
tr[u].w=min(tr[u].w,x);
tr[u].tag=min(tr[u].tag,x);
return;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)modify(u<<1,l,r,x);
if(mid<r)modify(u<<1|1,l,r,x);
pushup(u);
}
int query(int u,int l,int r)
{
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].w;
pushdown(u);
int mid=tr[u].l+tr[u].r>>1,res=0;
if(l<=mid)res=max(res,query(u<<1,l,r));
if(mid<r)res=max(res,query(u<<1|1,l,r));
return res;
}
int main()
{
freopen("hard.in","r",stdin);
freopen("hard.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++)scanf("%d%d",&M[i].l,&M[i].r);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].id=i;
}
sort(M+1,M+m+1,cmp);
sort(Q+1,Q+q+1,cmp);
build(1,1,n);
for(int l=n,mt=1,qt=1;l;l--)
{
while(mt<=m&&M[mt].l==l)
{
modify(1,M[mt].l,M[mt].r,M[mt].r);
mt++;
}
while(qt<=q&&Q[qt].l==l)
{
res[Q[qt].id]=(query(1,Q[qt].l,Q[qt].r)<=Q[qt].r);
qt++;
}
}
for(int i=1;i<=q;i++)puts(res[i]?"YES":"NO");
return 0;
}