晚测1

A:牛半仙的妹子图

spfa求出到每个点最少需要多少的困难接受能力
然后对于每个颜色求一下最少的困难接受能力
然后求出每个颜色对于当前次的l到r 贡献有多少
统计就可以了
因为觉得是原题 所以直接冲了个Kruscal
最小生成树
然后每次求出一个困难接受能力的答案是多少
然后前缀和维护一下区间的答案
最后直接用前缀和差分 以及边界情况的处理就可以了
但是需要套二分 而且需要离散化
写加调了一个半小时

show code

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
const int maxn = 5e5 + 10;
const int maxm = 1e3 + 10;
int fa[maxn],mp[maxn],head[maxn];
int u[maxn],v[maxn],w[maxn],c[maxn];
int tot,cnt;
ll sum[maxn];
ll Sum[maxn];
bitset<maxm> size[maxn];

struct Node{
	int id,w;
	friend bool operator <(const Node &A,const Node &B) {return A.w < B.w;}
}as[maxn];

struct node{
	int from,next,to,w;
	friend bool operator <(const node &A,const node &B) {return A.w < B.w;}
}a[maxn<<1];

void add(rint x,rint y,rint w){
	a[++cnt] = (node) {x,head[x],y,w}; head[x] = cnt;
}

int find(rint x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}

signed main(){
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	rint n,m,q,x,op,mod; scanf("%d%d%d%d%d",&n,&m,&q,&x,&op);
	if(op) scanf("%d",&mod);
	for(rint i = 1;i <= n;++i) scanf("%d",&c[i]),fa[i] = i,size[i][c[i]] = 1;
	for(rint i = 1;i <= m;++i) scanf("%d%d%d",&u[i],&v[i],&as[i].w),as[i].id = i;
	sort(as+1,as+m+1);
	for(rint i = 1;i <= m;++i) {
		if(as[i].w != as[i-1].w) tot++;
		w[as[i].id] = tot;
		mp[tot] = as[i].w;
	}
	for(rint i = 1;i <= m;++i) add(u[i],v[i],w[i]);
	sort(a+1,a+cnt+1);
	rint j = 1;
	for(rint i = 1;i <= tot;++i) {
		while(j <= cnt && a[j].w <= i) {
			rint u = a[j].from,v = a[j].to;
			rint fu = find(u),fv = find(v);
			if(fu == fv) {j++;continue;}
			fa[fu] = fv;
			size[fv] |= size[fu];
			j++;
		}
		sum[i] = size[find(x)].count();
		Sum[i] = Sum[i-1] + sum[i] * (mp[i+1] - mp[i]);
	}
	sum[0] = 1;
	ll last = 0;
	for(rint i = 1;i <= q;++i) {
		rint l,r; scanf("%d%d",&l,&r);
		if(op) l = (l ^ last) % mod + 1,r = (r ^ last) % mod + 1;
		if(l > r) swap(l,r);
		rint al = l,ar = r;
		rint L = 1,R = tot;
		while(L <= R) {
			rint mid = L + R >> 1;
			if(mp[mid] > l) R = mid - 1;
			else L = mid + 1;
		} l = R; 
		L = 1,R = tot;
		while(L <= R) {
			rint mid = L + R >> 1;
			if(mp[mid] > r) R = mid - 1;
			else L = mid + 1;
		} r = R;
		if(l == r) {
			last = (ar - mp[r]) * sum[r];
			last -= (al - 1 - mp[l]) * sum[l];
			printf("%lld
",last);
			continue;
		}
		last = 0;
		last += (ar - mp[r] + 1) * sum[r];
		last += (mp[l+1] - al) * sum[l];
		last += (Sum[r-1] - Sum[l]);
		printf("%lld
",last);
	}
	return 0;
}

##B:牛半仙的妹子Tree