QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90271#5830. 树FxorGCompile Error//C++146.7kb2023-03-22 16:31:442023-03-22 16:31:44

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-22 16:31:44]
  • 评测
查看
  • [2023-03-22 16:31:44]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
using namespace std;
const int N=(int)(1e6+1);
vector<int>g[N];
ll d[20][N],ans[N];
int t[2][N][20],num[20][N],v[N],n,q;

struct node {
	int x,dep,id,add;
	node(int X,int Dep,int Add,int Id) {
		x=X; dep=Dep; add=Add; id=Id;
	}
};
vector<node>vec[20];
vector<int>D[N];
int dep[N],id[N],idtot,sz[N],m;
void dfs0(int x,int ff) {
	dep[x]=dep[ff]+1; id[x]=++idtot; sz[x]=1;
	D[dep[x]].pb(id[x]);
	for(int y:g[x]) {
		if(y==ff) continue ;
		dfs0(y,x); sz[x]+=sz[y];
	}
}

namespace DS1 {
	ll sum[N*20];
	int rt[N],ls[N*20],rs[N*20],tot;
	void clr() {
		for(int i=1;i<=n;i++) rt[i]=0;
		for(int i=1;i<=tot;i++) ls[i]=rs[i]=sum[i]=0;
		tot=0;
	}
	void push_up(int cur) {
		sum[cur]=0;
		if(ls[cur]) sum[cur]=sum[ls[cur]];
		if(rs[cur]) sum[cur]+=sum[rs[cur]];
	}
	void upt(int &cur,int l,int r,int pos,int v) {
		if(!cur) cur=++tot;
		if(l==r) {
			sum[cur]=v; return ;
		}
		int mid=(l+r)>>1;
		if(pos<=mid) upt(ls[cur],l,mid,pos,v);
		else upt(rs[cur],mid+1,r,pos,v);
		push_up(cur);
	}
	ll qry(int cur,int l,int r,int cl,int cr) {
		if(!cur) return 0;
		if(cl<=l&&r<=cr) return sum[cur];
		int mid=(l+r)>>1;
		if(cr<=mid) return qry(ls[cur],l,mid,cl,cr);
		if(cl>mid) return qry(rs[cur],mid+1,r,cl,cr);
		return qry(ls[cur],l,mid,cl,cr)+qry(rs[cur],mid+1,r,cl,cr);
	}
}

namespace DS2 {
	int sum[N*20];
	int rt[N],ls[N*20],rs[N*20],tot;
	void clr() {
		for(int i=1;i<=n;i++) rt[i]=0;
		for(int i=1;i<=tot;i++) ls[i]=rs[i]=sum[i]=0;
		tot=0;
	}
	void push_up(int cur) {
		sum[cur]=0;
		if(ls[cur]) sum[cur]=sum[ls[cur]];
		if(rs[cur]) sum[cur]+=sum[rs[cur]];
	}
	void upt(int &cur,int l,int r,int pos,int v) {
		if(!cur) cur=++tot;
		if(l==r) {
			sum[cur]=v; return ;
		}
		int mid=(l+r)>>1;
		if(pos<=mid) upt(ls[cur],l,mid,pos,v);
		else upt(rs[cur],mid+1,r,pos,v);
		push_up(cur);
	}
	int qry(int cur,int l,int r,int cl,int cr) {
		if(!cur) return 0;
		if(cl<=l&&r<=cr) return sum[cur];
		int mid=(l+r)>>1;
		if(cr<=mid) return qry(ls[cur],l,mid,cl,cr);
		if(cl>mid) return qry(rs[cur],mid+1,r,cl,cr);
		return qry(ls[cur],l,mid,cl,cr)+qry(rs[cur],mid+1,r,cl,cr);
	}
}

namespace DS3 {
	int sum[N*20];
	int rt[N],ls[N*20],rs[N*20],tot;
	void clr() {
		for(int i=1;i<=n;i++) rt[i]=0;
		for(int i=1;i<=tot;i++) ls[i]=rs[i]=sum[i]=0;
		tot=0;
	}
	void push_up(int cur) {
		sum[cur]=0;
		if(ls[cur]) sum[cur]=sum[ls[cur]];
		if(rs[cur]) sum[cur]+=sum[rs[cur]];
	}
	void upt(int &cur,int l,int r,int pos,int v) {
		if(!cur) cur=++tot;
		if(l==r) {
			sum[cur]=v; return ;
		}
		int mid=(l+r)>>1;
		if(pos<=mid) upt(ls[cur],l,mid,pos,v);
		else upt(rs[cur],mid+1,r,pos,v);
		push_up(cur);
	}
	int qry(int cur,int l,int r,int cl,int cr) {
		if(!cur) return 0;
		if(cl<=l&&r<=cr) return sum[cur];
		int mid=(l+r)>>1;
		if(cr<=mid) return qry(ls[cur],l,mid,cl,cr);
		if(cl>mid) return qry(rs[cur],mid+1,r,cl,cr);
		return qry(ls[cur],l,mid,cl,cr)+qry(rs[cur],mid+1,r,cl,cr);
	}
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(false);
	cin>>n; m=0;
	for(int i=0;(1<<i)<=n;i++) m=i;
	for(int i=1;i<=n;i++) cin>>v[i]; 
	for(int i=2;i<=n;i++) {
		int x; cin>>x; g[x].pb(i);
	}
	dfs0(1,0);
	cin>>q;
	for(int i=1;i<=q;i++) {
		int x,K; cin>>x>>K; ++K; 
		int nw=0;
		for(int j=m;j>=0;j--) {
			if((K>>j)&1) {
				vec[j].pb(node(x,dep[x]+nw,nw,i));
				nw+=(1<<j);
			}
		}
	}
	
	for(int i=0;i<=m;i++) {
		if(!i) {
			for(int j=1;j<=n;j++) {
				d[0][j]=v[j]; num[0][j]=1;
				for(int k=0;k<=m;k++) {
					if((v[j]>>k)&1) ++t[0][j][k];
				}
			}
			DS1::clr(); DS2::clr(); DS3::clr();
			for(int j=1;j<=n;j++) DS1::upt(DS1::rt[dep[j]],1,n,id[j],d[i][j]),DS3::upt(DS3::rt[dep[j]],1,n,id[j],num[i][j]);
			for(int j=1;j<=n;j++) DS2::upt(DS2::rt[dep[j]],1,n,id[j],t[i&1][j][i]);
			for(int j=1;j<=n;j++) {
				int qwq=DS3::qry(DS3::rt[dep[j]+(1<<i)],1,n,id[j],id[j]+sz[j]-1)-2*DS2::qry(DS2::rt[dep[j]+(1<<i)],1,n,id[j],id[j]+sz[j]-1);
				d[i+1][j]=d[i][j]+DS1::qry(DS1::rt[dep[j]+(1<<i)],1,n,id[j],id[j]+sz[j]-1)+1ll*qwq*(1ll<<i);
				num[i+1][j]=num[i][j]+DS3::qry(DS1::rt[dep[j]+(1<<i)],1,n,id[j],id[j]+sz[j]-1);
//				cout<<num[i+1][j]<<' ';
			}
//			cout<<'\n';
			for(int k=0;k<=m;k++) {
				DS2::clr();
				for(int j=1;j<=n;j++) DS2::upt(DS2::rt[dep[j]],1,n,id[j],t[i&1][j][k]);
				for(int j=1;j<=n;j++)
					t[(i&1)^1][j][k]+=t[i&1][j][k]+DS2::qry(DS2::rt[dep[j]+(1<<i)],1,n,id[j],id[j]+sz[j]-1);
			}
			for(auto j:vec[i]) {
				ans[j.id]+=DS1::qry(DS1::rt[j.dep],1,n,id[j.x],id[j.x]+sz[j.x]-1);
			}
			for(int k=0;k<=m;k++) {
				DS2::clr();
				for(int j=1;j<=n;j++) DS2::upt(DS2::rt[dep[j]],1,n,id[j],t[i&1][j][k]);
				for(auto j:vec[i]) {
					if((j.add>>k)&1) {
						int qwq=DS3::qry(DS3::rt[j.dep],1,n,id[j.x],id[j.x]+sz[j.x]-1)-2*DS2::qry(DS2::rt[j.dep],1,n,id[j.x],id[j.x]+sz[j.x]-1);
//						cout<<i<<" "<<j.id<<" "<<j.x<<" "<<j.dep<<" "<<DS2::qry(DS2::rt[j.dep],1,n,id[j.x],id[j.x]+sz[j.x]-1)<<"mmm\n";
//						cout<<qwq<<'\n';
//						cout<<j.add<<" "<<(1<<i)<<'\n';
						ans[j.id]+=1ll*qwq*(1ll<<k);
					}
				}
			}
			continue ;
		}
		DS1::clr(); DS2::clr(); DS3::clr();
		for(int j=1;j<=n;j++) DS1::upt(DS1::rt[dep[j]],1,n,id[j],d[i][j]),DS3::upt(DS3::rt[dep[j]],1,n,id[j],num[i][j]);
		for(int j=1;j<=n;j++) DS2::upt(DS2::rt[dep[j]],1,n,id[j],t[i&1][j][i]);
		for(int j=1;j<=n;j++) {
			int qwq=DS3::qry(DS3::rt[dep[j]+(1<<i)],1,n,id[j],id[j]+sz[j]-1)-2*DS2::qry(DS2::rt[dep[j]+(1<<i)],1,n,id[j],id[j]+sz[j]-1);
//			cout<<DS3::qry(DS3::rt[dep[j]+(1<<i)],1,n,id[dep[j]+(1<<i)],id[j]+sz[j]-1)<<'\n';
			d[i+1][j]=d[i][j]+DS1::qry(DS1::rt[dep[j]+(1<<i)],1,n,id[j],id[j]+sz[j]-1)+1ll*qwq*(1ll<<i);
			num[i+1][j]=num[i][j]+DS3::qry(DS3::rt[dep[j]+(1<<i)],1,n,id[j],id[j]+sz[j]-1);
		}
		for(int k=0;k<=m;k++) {
			DS2::clr();
			for(int j=1;j<=n;j++) DS2::upt(DS2::rt[dep[j]],1,n,id[j],t[i&1][j][k]);
			for(int j=1;j<=n;j++)
				t[(i&1)^1][j][k]=t[i&1][j][k]+DS2::qry(DS2::rt[dep[j]+(1<<i)],1,n,id[j],id[j]+sz[j]-1);
		}
		for(auto j:vec[i]) {
			ans[j.id]+=DS1::qry(DS1::rt[j.dep],1,n,id[j.x],id[j.x]+sz[j.x]-1);
//			cout<<j.dep<<" "<<j.x<<" "<<DS1::qry(DS1::rt[j.dep],1,n,id[j.x],id[j.x]+sz[j.x]-1)<<'\n';
		}
		for(int k=0;k<=m;k++) {
			DS2::clr();
			for(int j=1;j<=n;j++) DS2::upt(DS2::rt[dep[j]],1,n,id[j],t[i&1][j][k]);
			for(auto j:vec[i]) {
				if((j.add>>k)&1) {
					int qwq=DS3::qry(DS3::rt[j.dep],1,n,id[j.x],id[j.x]+sz[j.x]-1)-2*DS2::qry(DS2::rt[j.dep],1,n,id[j.x],id[j.x]+sz[j.x]-1);
//					cout<<DS3::qry(DS3::rt[j.dep],1,n,id[j.x],id[j.x]+sz[j.x]-1)<<'\n';
//					cout<<"mmm\n";
					ans[j.id]+=1ll*qwq*(1ll<<k);
				}
			}
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
	return 0;
}
Source code, Language: C++14

Details 

/tmp/ccK7KqTX.o: in function `__tcf_0':
answer.code:(.text+0x58): relocation truncated to fit: R_X86_64_PC32 against symbol `g' defined in .bss section in /tmp/ccK7KqTX.o
/tmp/ccK7KqTX.o: in function `dfs0(long long, long long)':
answer.code:(.text+0x2007): relocation truncated to fit: R_X86_64_PC32 against symbol `g' defined in .bss section in /tmp/ccK7KqTX.o
/tmp/ccK7KqTX.o: in function `main':
answer.code:(.text.startup+0xd9): relocation truncated to fit: R_X86_64_PC32 against symbol `g' defined in .bss section in /tmp/ccK7KqTX.o
/tmp/ccK7KqTX.o: in function `_GLOBAL__sub_I_g':
answer.code:(.text.startup+0x3c91): relocation truncated to fit: R_X86_64_PC32 against `.bss'
answer.code:(.text.startup+0x3cb6): relocation truncated to fit: R_X86_64_PC32 against symbol `g' defined in .bss section in /tmp/ccK7KqTX.o
collect2: error: ld returned 1 exit status
English 繁體中文 简体中文

Server Time: 2024-12-02 18:09:31 | OpenSource Project