HDU多校1 - 6756 Finding a MEX(分块+二分+树状数组)

题目链接：点击查看

题目大意：给出一个 n 个点和 m 条边的无向图，每个点都有一个权值，现在需要执行 q 次操作，每次操作分为两种类型：

1 pos val ：将第 pos 个点的权值修改为 val

2 pos ：询问第 pos 个点相邻的所有点的权值组成的集合的 mex

题目分析：只能说数据水了，如果数据拉满 std 的复杂度应该是会 TLE 的

很显然的几个结论是：

设点 u 的度数为 du[ u ] ，则 mex( u ) 的答案一定小于等于 du[ u ]

度数大于等于 sqrt( n ) 的点的个数一定小于等于 sqrt( n ) 个

这样一来考虑 sqrt 分块，对于每个度数大于 sqrt( n ) 的结点维护一个树状数组，树状数组记录一下相邻的结点的权值都出现了哪些，这样就可以二分去统计出 mex 了

综上所述，对于操作 1 ，只需要更新 pos 结点周围所有度数大于 sqrt( n ) 的结点的树状数组就好了，因为最多只有 sqrt( n ) 个结点，最坏情况就是这个 pos 结点连接了 sqrt( n ) 个结点，对于每个节点的更新，只需要对树状数组进行单点更新，所以最坏的时间复杂度为 sqrt( n ) * log n

对于操作 2 ，如果 pos 节点的度数小于 sqrt( n ) 的话，直接暴力查询就好了，时间复杂度为 sqrt( n ) ，如果度数大于等于 sqrt( n ) 的话，就以 logn * logn 的时间复杂度在树状数组上二分就可以查询答案了

总的时间复杂度为 T * n * sqrt( n ) * logn

注意，因为对于这个思路来说，只需要对于度数大于等于 sqrt( n ) 建立一个更新 + 查询都是 log 级别的数据结构即可，也不难想到用 set 维护 0 ~ du[ i ] 内没有出现的数字，亦或者直接在线段树上二分，不过前者好像是常数太大，无论如何优化仍然 TLE，后者是因为区间大小问题不方便操作（或许可以用线段树AC，不过个人感觉树状数组来写这个题目更为简单）

代码：
 

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;vector<int>node[N],adj[N],c[N],cnt[N];int n,m,sz;bool vis[N];int a[N];inline int lowbit(int x) {return x&(-x); }void add(int u,int pos,int val) {int du=node[u].size();while(pos<=du){c[u][pos]+=val;pos+=lowbit(pos);} }int ask(int u,int pos) {int ans=0;while(pos){ans+=c[u][pos];pos-=lowbit(pos);}return ans; }void init() {for(int i=0;i<N;i++){adj[i].clear();node[i].clear();cnt[i].clear();c[i].clear();} }int get_mex1(int u)//暴力计算mex {int du=node[u].size();memset(vis,false,du+5);for(auto v:node[u])if(a[v]<=du)vis[a[v]]=true;int mex=0;while(vis[mex])mex++;return mex; }int get_mex2(int u)//树状数组计算mex {if(!cnt[u][0])//特判0 return 0;int l=1,r=node[u].size(),mex=-1;while(l<=r){int mid=l+r>>1;if(ask(u,mid)<mid){mex=mid;r=mid-1;}elsel=mid+1;}return mex; }void update(int u,int pre_val,int cur_val)//更新点u的一个相邻节点由pre_val变为cur_val {int du=node[u].size();if(cur_val<=du){if(!cnt[u][cur_val]&&cur_val)add(u,cur_val,1);cnt[u][cur_val]++;}if(pre_val<=du){cnt[u][pre_val]--;if(!cnt[u][pre_val]&&pre_val)add(u,pre_val,-1);} }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){init();scanf("%d%d",&n,&m);sz=sqrt(n);for(int i=1;i<=n;i++)scanf("%d",a+i);while(m--){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}for(int u=1;u<=n;u++)if(node[u].size()>=sz){int du=node[u].size();c[u].resize(du+5);cnt[u].resize(du+5);for(auto v:node[u]){adj[v].push_back(u);if(a[v]<=du){if(!cnt[u][a[v]]&&a[v])//因为树状数组是从1开始的，所以对于0我们需要特判add(u,a[v],1);cnt[u][a[v]]++;}}}int q;scanf("%d",&q);while(q--){int op;scanf("%d",&op);if(op==1){int pos,val;scanf("%d%d",&pos,&val);for(auto v:adj[pos])update(v,a[pos],val);a[pos]=val;}else{int pos;scanf("%d",&pos);if(node[pos].size()<sz)printf("%d\n",get_mex1(pos));elseprintf("%d\n",get_mex2(pos));}}}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU多校1 - 6756 Finding a MEX(分块+二分+树状数组)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。