妹子求卡常P7710
  • 板块学术版
  • 楼主_Eriri_
  • 当前回复10
  • 已保存回复10
  • 发布时间2024/4/25 21:00
  • 上次更新2024/4/26 10:00:42
查看原帖
妹子求卡常P7710
1008068
_Eriri_楼主2024/4/25 21:00
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+2;
const int B1=500; 
int B2=205;
namespace fast_IO{
    #define FASTIO
    #define IOSIZE 100000
    char ibuf[IOSIZE],obuf[IOSIZE];char*p1=ibuf,*p2=ibuf,*p3=obuf;
    #ifdef ONLINE_JUDGE
    #define getchar()((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
    #define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #endif
    #define isdigit(ch)(ch>47&&ch<58)
    #define isspace(ch)(ch<33)
    template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,true;}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}template<typename T>inline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}
    #ifdef _GLIBCXX_STRING
    inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}
    #endif
    template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a);print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;template<typename T>Fast_IO&operator>>(Fast_IO&io,T&b){return read(b),io;}template<typename T>Fast_IO&operator<<(Fast_IO&io,T b){return print(b),io;}
}using namespace fast_IO;
int n,m,fa[N],dep[N],sz[N],mx[N],son[N],dfn[N],dy[N],len[N],top[N];

//分块封装 

//o1改 o根查 

int st[N],en[N],pos[N],cnt; 
struct Block1{
	int pt[N],sum[1050]; 
	
	inline void add(int x,int val){
		pt[x]+=val;
		sum[pos[x]]+=val;
	}
	inline int Ask(int x){
		if(!x)return 0;
		int res=0;
		for(int i=1;i<pos[x];i+=4){
			res+=sum[i];
			if(i+1<pos[x])res+=sum[i+1];
			if(i+2<pos[x])res+=sum[i+2];
			if(i+3<pos[x])res+=sum[i+3];
		}
		for(int i=st[pos[x]];i<=x;i+=4){
			res+=pt[i];
			if(i+1<=x)res+=pt[i+1];
			if(i+2<=x)res+=pt[i+2];
			if(i+3<=x)res+=pt[i+3];			
		}
		return res;
	}
	inline void Add(int l,int r,int val){
		add(l,val);
		if(r+1<=n)add(r+1,-val);
	}

}Bf;


//o根改 o1查
struct Block2{
	int pt[N],lbj[1050]; 
	
	inline void add(int x,int val){
		for(int i=x;i<=en[pos[x]];i+=4){
			pt[i]+=val;
			if(i+1<=en[pos[x]])pt[i+1]+=val;
			if(i+2<=en[pos[x]])pt[i+2]+=val;
			if(i+3<=en[pos[x]])pt[i+3]+=val;
		}
		for(int i=pos[x]+1;i<=cnt;i+=4){
			lbj[i]+=val;
			if(i+1<=cnt)lbj[i+1]+=val;
			if(i+2<=cnt)lbj[i+2]+=val;
			if(i+3<=cnt)lbj[i+3]+=val;			
		}
	}
	inline int Ask(int x){
		return pt[x]+lbj[pos[x]];
	}
	inline void Add(int l,int r,int val){
		add(l,val);
		if(r+1<=n)add(r+1,-val);
	}
	
}Sum;
struct edge{
	int next;
	int to;
}ed[N];int ed_cnt;
int h[N];
void add_edge(int x,int y){
	ed[++ed_cnt]={h[x], y};
	h[x]=ed_cnt;
}

int lg[N];

int f[N][20];
int up[N];int uphead[N];
void dfs1(int u){
	sz[u]=1, mx[u]=dep[u]=dep[fa[u]]+1;
	for(int i=h[u];i;i=ed[i].next){
		int v=ed[i].to;
		dfs1(v);		
		if(mx[v]>mx[son[u]])son[u]=v;
		sz[u]+=sz[v];
		mx[u]=max(mx[u], mx[v]);
	}
}
void dfs2(int u,int head){
	dfn[u]=++dfn[0], dy[dfn[0]]=u;
	top[u]=head;
	len[head]++;
	if(son[u])dfs2(son[u],head);
	for(int i=h[u];i;i=ed[i].next){
		int v=ed[i].to;
		if(v==son[u])continue;
		dfs2(v,v);
	} 
}
int bfn[N], bdy[N];
int Ld[N], Rd[N];
queue<int> q;
void bfs(){
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		bfn[u]=++bfn[0], bdy[bfn[0]]=u;
		if(son[u])q.push(son[u]);
		for(int i=h[u];i;i=ed[i].next)if(ed[i].to!=son[u])q.push(ed[i].to); 
	}
}

struct opera{
	int id;
	int u;
	int x;
	int y;
	int val;
	bool operator < (const opera & b){
		if(x==b.x)return id<b.id;
		return x<b.x;
	}
}qs[N];int qcnt;
int ans[N], abj[N], apr[N];

int tdep[N];
int arr[N];
int ady[N];		
vector<int> tong1[N];
int tong2[N];
bool cmp(int x,int y){
	if(tdep[x]==tdep[y])return dfn[x]<dfn[y];
	return tdep[x]<tdep[y];
}

//O(1)k级祖先 
inline int Kfa(int u,int k){
	if(k<0)return 0;
	if(k==0)return u;
	if(k>dep[u])return 0;
	
	
	int cur=f[u][lg[k]-1];
	k-=(1<<(lg[k]-1));
	if(dep[cur]-dep[top[cur]]>=k)return dy[dfn[cur]-k];
	
	return up[uphead[top[cur]] + k-(dep[cur]-dep[top[cur]])-1];
}

inline void Check(int cur,int u,int k, int val){
	int L=bfn[cur],R=bfn[cur];
	int l=max(bfn[cur]-sz[u]+1, Ld[dep[cur]]), r=bfn[cur];
	l=bfn[cur], r=min(bfn[cur]+sz[u]-1, Rd[dep[cur]]);
	
	if(l!=r){
		if((r-l+1)<=12){
			for(int j=l+1;j<=r;j++)
				if(Kfa(bdy[j],k)==u)R=j;
				else break;			
		}
		else {
			while(l<=r){
				int mid=l+r>>1;
				int now=Kfa(bdy[mid], k);
				if(now==u)R=mid, l=mid+1;
				else r=mid-1;
			}			
		}	
	}
	Bf.Add(L,R,val);
}
int main(){
//	freopen("a.in","r",stdin);
//	freopen("me.out","w",stdout);
	
	io>>n>>m;
//	double ss=clock(); 
	//预处理dfs序bfs序倍增长剖分块 
	for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
	for(int i=2;i<=n;i++)io>>fa[i], add_edge(fa[i],i), f[i][0]=fa[i];
	for(int j=1;j<=log2(n);j++)
		for(int i=1;i<=n;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	dfs1(1);
 
	dfs2(1,1);
	bfs();
	B2=400; 
	for(int i=1;i<=n+1;i++)
		if(dep[bdy[i]]!=dep[bdy[i-1]])Ld[dep[bdy[i]]]=i, Rd[dep[bdy[i-1]]]=i-1;
	
	
	int ttl=0;
	for(int i=1;i<=n;i++)		
		if(top[i]==i){
			uphead[i]=ttl+1;
			for(int j=1, cur=fa[i];j<=len[i];j++, cur=fa[cur]){
				up[++ttl]=cur;
			}				
		}		

	for(int i=1;i<=n;i+=B1){
		++cnt;
		st[cnt]=i, en[cnt]=min(n,i+B1-1);
		for(int j=st[cnt];j<=en[cnt];j++)pos[j]=cnt;
	}
	for(int i=1;i<=m;i++){
		int op,u,x,y,val;
		io>>op>>u;
		if(op==1){
			io>>x>>y>>val;
			if(dep[u]+y > mx[u])continue;		
			if(x>B2){			
				int step=y, cur=dy[dfn[u]+y];
				Check(cur,u,step,val);
				while(dep[cur]+x<=mx[cur]){
					cur=dy[dfn[cur]+x], step+=x;
					Check(cur,u,step,val);
				}
			}
			else {							
				qs[++qcnt]={i,u,x,y,val};	
			}
		}else {
			ans[i]=Bf.Ask(bfn[u]);
			apr[++apr[0]]=i;
			abj[i]=u;
		}
	}
	
	sort(qs+1,qs+1+qcnt);
	
//	double tt=clock();
//	if((tt-ss)>2000)return 0;
	
	int p=1;
	for(int j=1;j<=apr[0];j++){
		if(apr[j]>qs[1].id){
			p=j;
			break;
		}
	}
	for(int i=1;i<=qcnt;i++){
		if(qs[i].x!=qs[i-1].x){
			
			for(int j=1;j<=n;j+=4){
				tdep[j]=dep[j]%qs[i].x;
				if(j+1<=n)tdep[j+1]=dep[j+1]%qs[i].x;
				if(j+2<=n)tdep[j+2]=dep[j+2]%qs[i].x;
				if(j+3<=n)tdep[j+3]=dep[j+3]%qs[i].x;
			}
		
			for(int j=1;j<=n;j++)tong2[dfn[j]]=j;
			for(int j=1;j<=n;j++)
				tong1[tdep[tong2[j]]].emplace_back(tong2[j]);
			
			int rk=0;
			for(int j=0;j<qs[i].x;j++)
				for(int k=0;k<tong1[j].size();k++)ady[tong1[j][k]]=++rk;
			
			for(int j=1;j<=n;j++)arr[ady[j]]=j;
			
			for(int j=0;j<qs[i].x;j++)tong1[j].clear();
			memset(Sum.pt,0,sizeof(Sum.pt));
			memset(Sum.lbj,0,sizeof(Sum.lbj));
			
			for(int j=1;j<=apr[0];j++){
				if(apr[j]>qs[i].id){
					p=j;
					break;
				}
			}
		}
		int u=qs[i].u, x=qs[i].x, y=qs[i].y, val=qs[i].val;
		int cur=dy[dfn[u]+y];
		int pos=ady[cur];
		int R=0;
		int l=pos, r=n; 
		while(l<=r){
			int mid=l+r>>1;
			if(tdep[arr[mid]]==tdep[cur] && Kfa(arr[mid], dep[arr[mid]]-dep[u]) ==u)R=mid,l=mid+1;
			else r=mid-1;					
		}
		Sum.Add(pos,R,val);
				
		int en=(qs[i+1].x!=qs[i].x ? m : qs[i+1].id-1);		
		while(p<=apr[0]&&apr[p] <= en){
			ans[apr[p]]+=Sum.Ask(ady[ abj[apr[p]] ]);
			++p;
		}	
	}
	
	
//	cerr<<tl<<'\n';
	for(int i=1;i<=m;i++)if(abj[i])cout<<ans[i]<<'\n';
	
	return 0;
}

95分TLE(o.o) 主要是x>B2的部分速度太慢(ノへ ̄、)

2024/4/25 21:00
加载中...