免备案网站怎么收录,上海亿网站建设,虚拟主机和网站空间,网站怎么营销Gym102832K. Ragdoll#xff08;CCPC长春#xff09;
题意#xff1a;
n个点#xff0c;每个点都有自己的权值aia_iai#xff0c;一开始第i个点在第i个集合里。 如果一对点(i,j)是bad当且仅当满足i和j在同一个集合里#xff0c;且gcd(ai,aj)ai⊕ajgcd(a_i,a_j)a_i⊕a…Gym102832K. RagdollCCPC长春
题意
n个点每个点都有自己的权值aia_iai一开始第i个点在第i个集合里。 如果一对点(i,j)是bad当且仅当满足i和j在同一个集合里且gcd(ai,aj)ai⊕ajgcd(a_i,a_j)a_i⊕a_jgcd(ai,aj)ai⊕aj 现在有3种操作:
新增一个点x(在新的一个集合里)值为v合并两个集合x和y将点x的值改为v
有m个操作请输出每次操作后有多少对点是bad
题解
一开始无从下手因为这个式子不知道该如何应用 这里有个很巧妙的转换ai⊕aj⩾∣ai−aj∣⩾gcd(ai,aj)a_i⊕a_j ⩾|a_i-a_j|⩾gcd(a_i,a_j)ai⊕aj⩾∣ai−aj∣⩾gcd(ai,aj),如果我们要让等式成立则需要满足
ai⊕aj∣ai−aj∣a_i⊕a_j|a_i-a_j|ai⊕aj∣ai−aj∣∣ai−aj∣gcd(ai,aj)|a_i-a_j|gcd(a_i,a_j)∣ai−aj∣gcd(ai,aj)
转换证明 a⊕ba−ba⊕ba-ba⊕ba−b这个式子是显然成立的用二进制思想去考虑 gcd(a,b)a−bgcd(a,b)a-bgcd(a,b)a−b:由于gcd(a,b)是b的因子gcd(a,b)是a的因子所以gcd(a,b)就是(a-b)的因子所以gcd(a,b)一定小于等于a-b
∣ai−aj∣gcd(ai,aj)|a_i-a_j|gcd(a_i,a_j)∣ai−aj∣gcd(ai,aj) ajaigcd(ai,aj)a_ja_igcd(a_i,a_j)ajaigcd(ai,aj)或者ajai−gcd(ai,aj)a_ja_i-gcd(a_i,a_j)ajai−gcd(ai,aj) 而gcd(ai,aj)gcd(a_i,a_j)gcd(ai,aj)是aia_iai的因子 因此我们可以枚举aia_iai,然后枚举aia_iai的因子这样就求出对于aia_iai而言合法的aja_jaj用vector存下来。相当于我们可以预处理出所有是bad的点对 我们再看三个操作这种集合操作都可以用并查集来维护 对于操作1就是新加一个集合 对于操作2合并两个集合如果我们直接盲目合并复杂度是O(n)这里用到启发式合并把小的集合合并到大的集合中这样复杂度降低为O(log) 对于操作3我们先去掉原先元素可能组成的bad点对改成数v后再加入新的bad点对 在每次操作中维护着答案如何维护呢因为我们预处理出所有点对合并时两个集合时就枚举小集合所有元素看大集合内有多少可以构成bad点对更新答案ans。修改数时就是删除原先加上新填 unordered_map速度更快 详细内容看代码
代码
#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 maxn5e59;
int n,m;
int a[maxn];
vectorintg[maxn];
int fa[maxn];
int sz[maxn];
ll ans0;
unordered_mapint,llmp[maxn];
int gcd(int a,int b){if(b)return gcd(b,a%b);return a;
}
int find(int x){if(fa[x]x)return x;return fa[x]find(fa[x]);
}
void work(int x){for(int i1;i*ix;i){//枚举因子 if(x%i0){int tmpx-i;if((tmp^x)gcd(tmp,x)tmp!0)//符合bad的点对 g[x].push_back(tmp);tmpxi; if((tmp^x)gcd(tmp,x)tmp200000)g[x].push_back(tmp);if(i!x/i){tmpx-x/i;if((tmp^x)gcd(tmp,x)tmp!0)g[x].push_back(tmp);tmpxx/i;if((tmp^x)gcd(tmp,x)tmp!200000)g[x].push_back(tmp);} }}
}
void merge(int x,int y){int fxfind(x);int fyfind(y);if(fxfy)//如果在一个集合退出 return ;//我们让fy是小集合用fy去合并到fx if(sz[fx]sz[fy]) swap(fx,fy);//合并时更新答案ans for(auto it:mp[fy]){//遍历小集合内的所有元素it.first
// coutit.firstit.firstendl;for(int i0;ig[it.first].size();i){
// printf(g[it.first].size()%d\n,g[it.first].size());
// printf(g[it.first][%d]%d\n,i,g[it.first][i]);//看大集合中有多少点可以与小集合的元素组成bad点对 if(mp[fx].count(g[it.first][i]))ans 1ll * it.second * mp[fx][g[it.first][i]];}}for(auto it:mp[fy]){//把fy的所有元素存放到集合fx中即合并 mp[fx][it.first]it.second;} mp[fy].clear();sz[fx]sz[fy];fa[fy]fx;
}
int main()
{rd_test();for(int i1;i200002;i){work(i);//预处理出所有bad点对 }cinnm;for(int i1;inm;i){fa[i]i; sz[i]1;//集合大小}for(int i1;in;i){cina[i];mp[i][a[i]];//每个集合元素以及大小 }for(int i1;im;i){//添加 int op,x,y;cinopxy;if(op1){a[x]y;sz[x]1;mp[x][y]1;}else if(op2){//合并操作 merge(x,y);}else if(op3){//修改值 int ufind(x);for(int i0;ig[a[x]].size();i){//删除原集合内的bad点对 if(mp[u].count(g[a[x]][i]))ans-mp[u][g[a[x]][i]]; }mp[u][a[x]]--;//点a[x]删除a[x]y;//修改新值for(int i0;ig[a[x]].size();i){if(mp[u].count(g[a[x]][i]))ansmp[u][g[a[x]][i]]; }mp[u][a[x]];//加上新点 }printf(%lld\n,ans); }return 0;//Time_test();
}
