QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1219#645378#7626. Quake and Rebuildrotcar07Displace_Success!2024-11-20 20:26:182024-11-20 20:26:19

Details

Extra Test:

Time Limit Exceeded

input:

200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000...

result:


IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#645378#7626. Quake and RebuildDisplace_TL 2756ms9172kbC++143.2kb2024-10-16 18:01:002024-11-20 20:31:16

answer

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int N=2e5+5;
const int B=600;
int n, m;
int lp[B], rp[B], bid[N];
int fa[N], nxt[N], dis[N];
int ins[N];
int dt[B];
inline void rebuild(int i){
	if(dt[i]>=B) return ;
	for(int j=lp[i]; j<=rp[i]; ++j){
		int x=j; dis[j]=0;
		while(x>=lp[i]) ++dis[j], x=max(1, fa[x]-dt[i]);
		nxt[j]=x;
	}
}
#define gf(x) (dt[bid[x]]<B?nxt[x]:max(1, fa[x]-dt[bid[x]]))
inline int lca(int x, int y){
	while(gf(x)^gf(y)){
		if(x<y) y=gf(y);
		else x=gf(x);
	}
	if(bid[x]!=bid[y]) return gf(x);
	while(x^y){
		if(x<y) y=max(1, fa[y]-dt[bid[y]]);
		else x=max(1, fa[x]-dt[bid[x]]);
	}
	return x;
}
inline int dep(int x){
	int ret=0;
	while(x^1){
		if(dt[bid[x]]<B) ret+=dis[x], x=nxt[x];
		else ++ret, x=max(1, fa[x]-dt[bid[x]]);
	}
	return ret;
}
inline int getd(int x, int y){
	if(x==y) return 0;
	return dep(x)+dep(y)-2*dep(lca(x, y));
}
inline int jump(int x, int t){
	while(true) {
		while(gf(x)>t) x=gf(x);
		if(max(1, fa[x]-dt[bid[x]])>t) x=max(1, fa[x]-dt[bid[x]]);
		else return x;
	}
}
inline bool cmp(int x, int y){
	if(x==y)  return false;
	int t=lca(x, y);
	if(t==x) return true;
	if(t==y) return false;
	return jump(x, t)<jump(y, t);
}
bool occ[N];
int main(){
	// freopen("D:\\nya\\acm\\B\\test.in","r",stdin);
	// freopen("D:\\nya\\acm\\B\\test.out","w",stdout);
	read(n); read(m);
	for(int i=2; i<=n; ++i) read(fa[i]);
	for(int i=2; i<=n; ++i) bid[i]=(i-2)/B+1;
	bid[1]=0; 
	lp[0]=rp[0]=1; dt[0]=B;
	for(int i=1; i<=bid[n]; ++i) lp[i]=rp[i-1]+1, rp[i]=rp[i-1]+B;
	rp[bid[n]]=n;
	for(int i=1; i<=bid[n]; ++i) rebuild(i);
	while(m--){
		int op; read(op);
		if(op==1){
			int l, r, d; read(l); read(r); read(d);
			if(bid[l]==bid[r]){
				for(int i=l; i<=r; ++i) fa[i]-=d, fa[i]=max(fa[i], 0);
				rebuild(bid[l]);
				continue;
			}
			for(int i=l; i<=rp[bid[l]]; ++i) fa[i]-=d, fa[i]=max(fa[i], 0);
			rebuild(bid[l]);
			for(int i=lp[bid[r]]; i<=r; ++i) fa[i]-=d, fa[i]=max(fa[i], 0);
			rebuild(bid[r]);
			for(int i=bid[l]+1; i<bid[r]; ++i){
				dt[i]+=d; dt[i]=min(dt[i], n); rebuild(i);
			}
		}
		else{
			int k, x; 
			read(k);
			if(k==0){
				printf("0\n");
				continue;
			}
			vector<int> vec;
			while(k--){
				read(x); if(!ins[x]) vec.ep(x), ins[x]=1;
			}
			if(vec.size()>=B){
				int lc=vec[0];
				for(auto t:vec) lc=lca(lc, t);
				int ans=1;
				for(int i=n; i>lc; --i) if(ins[i]) ++ans, ins[max(1, fa[i]-dt[bid[i]])]=1, ins[i]=0;
				ins[lc]=0;
				printf("%d\n", ans);
				continue;
			}
			sort(vec.begin(), vec.end(), cmp);
			vec.ep(vec[0]);
			int ans=0;
			for(int i=1; i<(int)vec.size(); ++i) ans+=getd(vec[i-1], vec[i]);
			ans>>=1;
			for(auto t:vec) ins[t]=0;
			printf("%d\n", ans+1);
		}
	}
	return 0;
}