织梦做中英文网站步骤,绍兴越城区建设局网站,电脑商业网站怎的做,中国十大网络公司排行榜题面 $ solution: $ 真的没有想到可以用分块。 但是可以发现一个性质#xff0c;每个询问只关心这个点最后一次赋值操作#xff0c;和这个赋值操作后的所有取 $ min $ 操作。这个感觉很有用#xff0c;但是真的很难让人想到低于 $ n\times m $ 的做法。基于 $ DAG $ 的数据结… 题面 $ solution: $ 真的没有想到可以用分块。 但是可以发现一个性质每个询问只关心这个点最后一次赋值操作和这个赋值操作后的所有取 $ min $ 操作。这个感觉很有用但是真的很难让人想到低于 $ n\times m $ 的做法。基于 $ DAG $ 的数据结构是目前很少需要掌握的好吧我都不知道有什么数据结构可以维护 $ DAG $ 所以肯定得骚操作。 我们可以发现一个 $ DAG $ 的性质如果有一连串赋值操作我们可以根据拓扑序 $ O(n) $ 将所有操作完成直接按顺序从后往前赋值这样每个点赋值之后就不会再被访问。同理的 如果有一连串取 $ min $ 操作我们也可以根据拓扑序 $ O(n) $ 将所有操作完成直接 $ min $ 值从小到大取 $ min $ 这样每个点在取 $ min $ 之后就不会再被访问。但是当我们将这两种操作合到一起时就不行了。 但是联想一下上面说的性质每个询问只关心这个点最后一次赋值操作和这个赋值操作后的所有取 $ min $ 操作。我们可以搞出一个分块来先预处理2操作将2操作序列分块并将每一块用上面的方法统计出每个结点在每个块内的取 $ min $ 后的值初值inf。然后我们就可以 $ \sqrt{n} $ 的求出任意一个区间里某个节点取 $ min $ 的最小值其实还需要一个操作。然后我们只需要快速找到每个询问的节点的最后一次赋值操作的编号即赋值的大小就可以得到答案。找到这个编号我们可以对1操作分块来完成。 但是上述操作我们还需要知道一个东西因为分块两边的小区间是要暴力遍历的这个我们需要知道每个操作能否对某个点产生影响这个等同于我们要知道 $ DAG $ 中一个点能否到另一个点。这个很奇妙的我们可以用 $ bitset $ 暴力完成。因为这个是无法用低于 $ n\times m $ 的复杂度完成但是只涉及能否我们可以用二进制。 仔细分析求得答案需要什么关键信息对于一连串操作可以一次完成就考虑分治或分块对于两种操作会互相影响考虑先预处理一种操作在进行第二种操作二进制和是与否这个对于复杂度优化很好用。$ DAG $ 中的一些问题是难以用低于 $ n\times m $ 的做法完成的 $ code: $ #includeiostream
#includecstdio
#includeiomanip
#includealgorithm
#includecstring
#includecstdlib
#includectime
#includecmath
#includevector
#includequeue
#includemap
#includeset
#includebitset#define ll long long
#define db double
#define rg register intusing namespace std;int tt,t1;
int n,m,q,ff;
int a[100005];
int idx[100005];
int fq[100005];
int fm[100005][404];
int vis[100005];
bitset100005 f[100005];struct su{int to,next;
}b[200005];
int tou[100005];struct pi{int id,x,v,op;inline bool operator (const pi i)const{return vi.v;}
}s[100005],k[100005];inline int qr(){register char ch; register bool sign0; rg res0;while(!isdigit(chgetchar()))if(ch-)sign1;while(isdigit(ch))resres*10(ch^48),chgetchar();if(sign)return -res; else return res;
}inline void yu(int i){ //预处理dag中两点是否可达vis[i]1; f[i][i]1;for(rg jtou[i];j;jb[j].next){if(!vis[b[j].to]) yu(b[j].to);f[i]|f[b[j].to];}
}inline void dfs(int i,int v,int time,bool op){ //修改操作if(vis[i]t)return ; else vis[i]t; //根据op判断是1操作还是2操作if(op) a[i]v,idx[i]time; else fm[i][time]v;for(rg jtou[i];j;jb[j].next){if(vis[b[j].to]t)continue;dfs(b[j].to,v,time,op);}
}int main(){//freopen(dag.in,r,stdin);//freopen(dag.out,w,stdout);nqr(); mqr(); qqr(); ffsqrt(q-1)1;for(rg i1;iq;i) fq[i](i-1)/ff1; //分块for(rg i1;im;i){rg xqr(),yqr();b[i]su{y,tou[x]}; tou[x]i;}for(rg i1;in;i) if(!vis[i])yu(i);for(rg i1;iq;i){ //先预处理每个块内的2操作rg opqr(); s[i]pi{i,qr(),0,op};if(op2) s[i].vqr();if(op2) k[tt]s[i];if(fq[i]!fq[i1]){sort(k1,ktt1); t; //从小到大保证每个点只修改一次for(rg j1;jn;j) fm[j][fq[i]]1e9; //赋初值for(rg j1;jtt;j)dfs(k[j].x,k[j].v,fq[i],0);tt0;}}for(rg i1;iq;i){if(s[i].op3){rg xs[i].x,yidx[x],va[x],sf0;for(rg ji;fq[j]fq[i];--j){ //在同一个块内暴力处理if(s[j].op1f[s[j].x][x]){ sf1; yj; vs[j].v;for(rg oy;oi;o)if(s[o].op2f[s[o].x][x]) vmin(v,s[o].v);break;}}if(!sf){ //这个if调了半个上午for(rg jy1;fq[j]fq[y];j) //前小块if(s[j].op2f[s[j].x][x]) vmin(v,s[j].v);for(rg jfq[y]1;jfq[i]-1;j) vmin(v,fm[x][j]); //中间的大块for(rg ji;fq[j]fq[i];--j) //后小块if(s[j].op2f[s[j].x][x]) vmin(v,s[j].v);}printf(%d\n,v);}if(fq[i]!fq[i1]){ t; //将这个块内的1操作一遍做完for(rg ji;fq[j]fq[i];--j)if(s[j].op1)dfs(s[j].x,s[j].v,j,1);}}return 0;
}转载于:https://www.cnblogs.com/812-xiao-wen/p/11505436.html
