如何给网站更换域名,网站备案 拍照网点,wordpress手机版加搜索,wordpress statraqJ Red-Black Paths(ICPC网络赛第一场)
题意#xff1a;
有n个点#xff0c;m次操作#xff0c;有三种操作#xff1a; 1 u v#xff1a;从u向v建一个有向边 2 u#xff1a;将点u染成红色 3 u: 将点u染成黑色 4 查询最新生成的红黑边的异或值 红黑边的值为#xff1a;∑…J Red-Black Paths(ICPC网络赛第一场)
题意
有n个点m次操作有三种操作 1 u v从u向v建一个有向边 2 u将点u染成红色 3 u: 将点u染成黑色 4 查询最新生成的红黑边的异或值 红黑边的值为∑1ilength(path)ni∗i\sum_{1ilength(path)}n_{i}*i∑1ilength(path)ni∗i
题解
题解参考 goto_1600 黑夜和白天 因为题目要求的是红黑路径的异或值那么如果一个点不在红黑路径那这个点就没啥用所以我们重新构图将一些无关紧要的点去掉 题目保证了∑红黑路5000000\sum红黑路5000000∑红黑路5000000,所以处理后我们就可以跑 因为操作很多我们可以考虑离线操作对于每个操作都有时间戳对于一个红黑路我们记录其路径上最后一次修改的时间戳tim并在用数组ans[tim]来记录这个路径的异或值 因为每次询问的是新增红黑路的异或值 我们在ans上记录的每个红黑路径最后一次修改的时间所对应的异或值 就比如下面这个数据第5个位置是28也就是在第5时刻一个红黑路最终形成且该路径的异或值为28很显然如果我们所询问的时间戳tim如果在[5,7]之间答案都是28我们该如何实现快速查询呢
0 0 0 0 28 0 0 19 0 0 23 31 0我们将ans从前往后异或一遍ans[i]^ans[i-1],此时ans[i]相当于第i时刻所有路径的异或值此时的异或值相当于是上一次路径和本次路径的异或那么本次异或值就是和上次询问的异或(再异或相当于消除)。你可以理解成两个图所有路径的xor值相同的被xor没了剩下的就是新增的红黑路
0 0 0 0 28 28 28 15 15 15 24 7 7代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn5e69;
vectorintQ;
vectorintR;
int black[maxn];
int red[maxn];
struct edge{int u,v,tim;
};
vectoredgee;
vectorPIIvec[maxn];
int vis[maxn];
int tag[maxn];
ll ans[maxn];
void dfs(int u){vis[u]1;if(black[u])tag[u]1;for(auto it:vec[u]){int vit.first;int wit.second;if(vis[v]){tag[u]|tag[v];continue;}dfs(v);tag[u]|tag[v];}
}
void rebuild(){for(int i0;i5000000;i)vec[i].clear();for(auto it:e){if(tag[it.u]tag[it.v]){vec[it.u].push_back({it.v,it.tim});}}
}
void path(int u,int maxx,ll sum,int dep){if(black[u]){int timmax(maxx,black[u]);ans[tim]^sum;}for(auto it:vec[u]){int vit.first;int timit.second;path(v,max(maxx,tim),sum1ll*dep*v,dep1);}}
int main()
{rd_test();int n;read(n);for(int i1;in;i){int op,u,v;read(op);if(op1){read(u,v);vec[u].push_back({v,i});e.push_back({u,v,i});}else if(op2){int u;cinu;R.push_back(u);red[u]i;}else if(op3){cinu;black[u]i;}else if(op4){Q.push_back(i);}}for(auto v:R){if(!vis[v])dfs(v); }rebuild();for(auto v:R){path(v,red[v],1ll*v,2);}for(int i1;in;i)ans[i]^ans[i-1];ll res0;for(int i0;iQ.size();i){resans[Q[i]];if(i) res^ans[Q[i-1]];coutresendl;}return 0;//Time_test();
}
