0pts 输出负数求助
查看原帖
0pts 输出负数求助
537998
lpx2024楼主2024/8/27 20:15

开longlong也没用

#include<bits/stdc++.h>
using namespace std;
const int maxN=60010;
struct node{
	int p,id;
};
int a[maxN],X[maxN],Y[maxN],c[maxN],l[maxN],r[maxN],tag[maxN],dfn[maxN],last[maxN],fa[maxN],fa2[maxN],fa3[maxN],lca[maxN],stp;
string s[maxN];
vector<int> v[maxN];
vector<node> Q[maxN];
int Find(int x){
	if(fa2[x]==x) return x;
	else return fa2[x]=Find(fa2[x]);
}
int Find_3(int x){
	if(fa3[x]==x) return x;
	else return fa3[x]=Find(fa3[x]);
}
void Merge(int x,int y){
	x=Find(x),y=Find(y);
	fa2[y]=x;
}
void build(int x,int y,int k){
	l[k]=x,r[k]=y;
	if(x==y) return;
	int mid=(l[k]+r[k])/2;
	build(x,mid,k*2);
	build(mid+1,y,k*2+1);
}
void update(int x,int y,int v,int k){
	if(x<=l[k] && y>=r[k]){
		c[k]+=v;
		return;
	}
	int mid=(l[k]+r[k])/2;
	if(x<=mid) update(x,y,v,k*2);
	if(y>mid) update(x,y,v,k*2+1);
}
int query(int x,int k){
	if(!x) return 0;
	if(l[k]==r[k]) return c[k];
	int mid=(l[k]+r[k])/2;
	if(x<=mid) return query(x,k*2)+c[k];
	else return query(x,k*2+1)+c[k];
}
void dfs(int x){
	dfn[x]=last[x]=++stp;
	for(int i=0;i<Q[x].size();i++){
		lca[Q[x][i].id]=Find_3(Q[x][i].p);
	}
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i];
		if(fa[x]==y) continue;
		fa[y]=x;
		dfs(y);
		last[x]=max(last[x],last[y]);
		fa3[y]=x;
	}
}
int main(){
	int n,q;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		fa2[i]=fa3[i]=i;
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		cin>>s[i]>>X[i]>>Y[i];
		if(s[i]=="bridge"){
			if(Find(X[i])!=Find(Y[i])){
				v[X[i]].push_back(Y[i]);
				v[Y[i]].push_back(X[i]);
				Merge(X[i],Y[i]);
			}
		} else if(s[i]=="excursion"){
			Q[X[i]].push_back(node{Y[i],i});
			Q[Y[i]].push_back(node{X[i],i});
		}
	}
	dfs(1);
	build(1,n,1);
	for(int i=1;i<=n;i++){
		update(dfn[i],last[i],a[i],1);
		fa2[i]=i;
	}
	for(int i=1;i<=q;i++){
		if(s[i]=="bridge"){
			if(Find(X[i])==Find(Y[i])){
				printf("no\n");
			} else {
				printf("yes\n");
				Merge(X[i],Y[i]);
			}
		} else if(s[i]=="penguins"){
			update(dfn[X[i]],last[X[i]],Y[i]-a[X[i]],1);
			a[X[i]]=Y[i];
		} else {
			if(Find(X[i])!=Find(Y[i])) printf("impossible\n");
			else printf("%d\n",query(dfn[X[i]],1)+query(dfn[Y[i]],1)-query(dfn[lca[i]],1)-query(dfn[fa[lca[i]]],1));
		}
	}
	return 0;
}#include<bits/stdc++.h>
using namespace std;
const int maxN=60010;
struct node{
	int p,id;
};
int a[maxN],X[maxN],Y[maxN],c[maxN],l[maxN],r[maxN],tag[maxN],dfn[maxN],last[maxN],fa[maxN],fa2[maxN],fa3[maxN],lca[maxN],stp;
string s[maxN];
vector<int> v[maxN];
vector<node> Q[maxN];
int Find(int x){
	if(fa2[x]==x) return x;
	else return fa2[x]=Find(fa2[x]);
}
int Find_3(int x){
	if(fa3[x]==x) return x;
	else return fa3[x]=Find(fa3[x]);
}
void Merge(int x,int y){
	x=Find(x),y=Find(y);
	fa2[y]=x;
}
void build(int x,int y,int k){
	l[k]=x,r[k]=y;
	if(x==y) return;
	int mid=(l[k]+r[k])/2;
	build(x,mid,k*2);
	build(mid+1,y,k*2+1);
}
void update(int x,int y,int v,int k){
	if(x<=l[k] && y>=r[k]){
		c[k]+=v;
		return;
	}
	int mid=(l[k]+r[k])/2;
	if(x<=mid) update(x,y,v,k*2);
	if(y>mid) update(x,y,v,k*2+1);
}
int query(int x,int k){
	if(!x) return 0;
	if(l[k]==r[k]) return c[k];
	int mid=(l[k]+r[k])/2;
	if(x<=mid) return query(x,k*2)+c[k];
	else return query(x,k*2+1)+c[k];
}
void dfs(int x){
	dfn[x]=last[x]=++stp;
	for(int i=0;i<Q[x].size();i++){
		lca[Q[x][i].id]=Find_3(Q[x][i].p);
	}
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i];
		if(fa[x]==y) continue;
		fa[y]=x;
		dfs(y);
		last[x]=max(last[x],last[y]);
		fa3[y]=x;
	}
}
int main(){
	int n,q;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		fa2[i]=fa3[i]=i;
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		cin>>s[i]>>X[i]>>Y[i];
		if(s[i]=="bridge"){
			if(Find(X[i])!=Find(Y[i])){
				v[X[i]].push_back(Y[i]);
				v[Y[i]].push_back(X[i]);
				Merge(X[i],Y[i]);
			}
		} else if(s[i]=="excursion"){
			Q[X[i]].push_back(node{Y[i],i});
			Q[Y[i]].push_back(node{X[i],i});
		}
	}
	dfs(1);
	build(1,n,1);
	for(int i=1;i<=n;i++){
		update(dfn[i],last[i],a[i],1);
		fa2[i]=i;
	}
	for(int i=1;i<=q;i++){
		if(s[i]=="bridge"){
			if(Find(X[i])==Find(Y[i])){
				printf("no\n");
			} else {
				printf("yes\n");
				Merge(X[i],Y[i]);
			}
		} else if(s[i]=="penguins"){
			update(dfn[X[i]],last[X[i]],Y[i]-a[X[i]],1);
			a[X[i]]=Y[i];
		} else {
			if(Find(X[i])!=Find(Y[i])) printf("impossible\n");
			else printf("%d\n",query(dfn[X[i]],1)+query(dfn[Y[i]],1)-query(dfn[lca[i]],1)-query(dfn[fa[lca[i]]],1));
		}
	}
	return 0;
}#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxN=900010;
struct node{
	int p,id;
};
int a[maxN],X[maxN],Y[maxN],c[maxN],l[maxN],r[maxN],tag[maxN],dfn[maxN],last[maxN],fa[maxN],fa2[maxN],fa3[maxN],lca[maxN],stp;
string s[maxN];
vector<int> v[maxN];
vector<node> Q[maxN];
int Find(int x){
	if(fa2[x]==x) return x;
	else return fa2[x]=Find(fa2[x]);
}
int Find_3(int x){
	if(fa3[x]==x) return x;
	else return fa3[x]=Find(fa3[x]);
}
void Merge(int x,int y){
	x=Find(x),y=Find(y);
	fa2[y]=x;
}
void build(int x,int y,int k){
	l[k]=x,r[k]=y;
	if(x==y) return;
	int mid=(l[k]+r[k])/2;
	build(x,mid,k*2);
	build(mid+1,y,k*2+1);
}
void update(int x,int y,int v,int k){
	if(x<=l[k] && y>=r[k]){
		c[k]+=v;
		return;
	}
	int mid=(l[k]+r[k])/2;
	if(x<=mid) update(x,y,v,k*2);
	if(y>mid) update(x,y,v,k*2+1);
}
int query(int x,int k){
	if(!x) return 0;
	if(l[k]==r[k]) return c[k];
	int mid=(l[k]+r[k])/2;
	if(x<=mid) return query(x,k*2)+c[k];
	else return query(x,k*2+1)+c[k];
}
void dfs(int x){
	dfn[x]=last[x]=++stp;
	for(int i=0;i<Q[x].size();i++){
		lca[Q[x][i].id]=Find_3(Q[x][i].p);
	}
	for(int i=0;i<v[x].size();i++){
		int y=v[x][i];
		if(fa[x]==y) continue;
		fa[y]=x;
		dfs(y);
		last[x]=max(last[x],last[y]);
		fa3[y]=x;
	}
}
signed main(){
	int n,q;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		fa2[i]=fa3[i]=i;
	}
	scanf("%lld",&q);
	for(int i=1;i<=q;i++){
		cin>>s[i]>>X[i]>>Y[i];
		if(s[i]=="bridge"){
			if(Find(X[i])!=Find(Y[i])){
				v[X[i]].push_back(Y[i]);
				v[Y[i]].push_back(X[i]);
				Merge(X[i],Y[i]);
			}
		} else if(s[i]=="excursion"){
			Q[X[i]].push_back(node{Y[i],i});
			Q[Y[i]].push_back(node{X[i],i});
		}
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) dfs(i);
	}
	build(1,n,1);
	for(int i=1;i<=n;i++){
		update(dfn[i],last[i],a[i],1);
		fa2[i]=i;
	}
	for(int i=1;i<=q;i++){
		if(s[i]=="bridge"){
			if(Find(X[i])==Find(Y[i])){
				printf("no\n");
			} else {
				printf("yes\n");
				Merge(X[i],Y[i]);
			}
		} else if(s[i]=="penguins"){
			update(dfn[X[i]],last[X[i]],Y[i]-a[X[i]],1);
			a[X[i]]=Y[i];
		} else {
			if(Find(X[i])!=Find(Y[i])) printf("impossible\n");
			else printf("%lld\n",query(dfn[X[i]],1)+query(dfn[Y[i]],1)-query(dfn[lca[i]],1)-query(dfn[fa[lca[i]]],1));
		}
	}
	return 0;
}
2024/8/27 20:15