牛客寒训营2 F(写的乱七八糟过的，赛后发现是并查集)

题目 题意: 给定n个数，由n-1个+或连接。有m次查询，永久修改a[x] = y，求整个式子的值。 思路: 用并查集把所有先处理完，然后+上。若修改的数两边都是+，直接求差值；否则，修改它父亲的累乘值，求差值。   我先求出了*对应的影响区间，然后用map映射了每个点的对应区间，这波太lao了。 时间复杂度: O(n * α(n) + m) 代码:

// Problem: 小沙的算数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23477/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i>= 1;
	}
	return res;
}
ll ni(ll x)
{
	return qpow(x,mod-2);
}
int find(int x)
{
	return x==fa[x]?x:fa[x] = find(fa[x]);
}
void Merge(int u,int v)
{
	u = find(u),v = find(v);
	if(u != v)
	{
		fa[v] = u;
		cnt[u] = cnt[u] * cnt[v] % mod;
	}
}
void solve()
{
   read(n); read(m);
   cin>>s;
   for(int i=1;is;
   for(int i=1;i