QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#642246#7626. Quake and RebuildfryanTL 540ms3796kbC++172.3kb2024-10-15 12:19:512024-10-15 12:19:52

Judging History

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

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2024-10-15 12:19:52]
  • 评测
  • 测评结果:TL
  • 用时:540ms
  • 内存:3796kb
  • [2024-10-15 12:19:51]
  • 提交

answer

#pragma once
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int mxn = 2e5+5;
const int bsz = 300; //change
const int nbk = mxn/bsz+1;

int n,m;
int fa[mxn];
int nx[mxn];
int lz[nbk];

inline int nex(int v) {
	if (lz[v/bsz] >= bsz) {
		return max(fa[v]+lz[v/bsz],0);
	}
	return nx[v];
}

inline void manual_update(int v) {
	int f = max(fa[v]+lz[v/bsz],0);
	if (f/bsz != v/bsz) {
		nx[v] = f;
	} else {
		nx[v] = nex(f);
	}
}

int lca(int a, int b) {
	while (1) {
		if (a < b) swap(a,b);
		//a > b
		int na = nex(a);
		int nb = nex(b);
		if (na != nb) {
			a = na;
		} else {
			break;
		}
	}
	while (1) {
		if (a==b) return a;
		if (a < b) swap(a,b);
		a = max(fa[a]+lz[a/bsz],0);
	}
	exit(1);
}

void quake(int l, int r, int d) {
	for (int i=l; i%bsz && i<=r; i++) {
		fa[i] -= d;
		manual_update(i);
	}
	
	int lb = (l+bsz-1)/bsz;
	int rb = r/bsz-1;
	for (int i=lb; i<=rb; i++) {
		lz[i] -= d;
		if (-lz[i] < bsz) {
			//manual update
			for (int j=i*bsz; j<(i+1)*bsz; j++) {
				manual_update(j);
			}
		}
	}
	//do right update
	if (r/bsz != l/bsz) {
		for (int i=bsz*(r/bsz); i<=r; i++) {
			fa[i] -= d;
			manual_update(i);
		}
	}
}

void rebuild(vector<int> &val) {
	set<int> ans;
	sort(all(val));
	val.erase(unique(all(val)),val.end());
	for (int i=0; i<sz(val); i++) {
		for (int j=i+1; j<sz(val); j++) {
			int R = lca(val[i],val[j]);
			int v = val[i];			
			ans.insert(R);
			while (v != R) {
				ans.insert(v);
				v = max(fa[v]+lz[v/bsz],0);
			}
			v = val[j];
			while (v != R) {
				ans.insert(v);
				v = max(fa[v]+lz[v/bsz],0);
			}
		}
	}
	cout<<sz(ans)<<"\n";
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n>>m;
	
	for (int i=1; i<n; i++) {
		cin>>fa[i]; --fa[i];
	}
	
	//build nx
	for (int i=0; i<n; i++) {
		if (fa[i]/bsz == i/bsz) {
			nx[i] = nx[fa[i]];
		} else {
			nx[i] = fa[i];
		}
	}
	
	while (m--) {
		int t; cin>>t;
		if (t==1) {
			//quake
			int l,r,d; cin>>l>>r>>d;
			quake(l-1,r-1,d);
		} else {
			int k; cin>>k;
			vector<int> val;
			for (int i=0; i<k; i++) {
				int x; cin>>x; --x;
				val.push_back(x);
			}
			rebuild(val);
		}
	}
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

input:

4 5
1 2 2
2 2 1 4
1 2 3 1
2 3 2 3 4
1 4 4 1
2 2 3 4

output:

3
4
3

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

10 10
1 2 3 3 4 5 7 7 9
1 2 10 3
2 9 9 5 3 10 7 2 4 6 8
1 6 10 3
1 2 7 3
1 7 10 3
2 2 4 3
2 3 7 4 4
1 3 9 3
1 3 9 3
1 10 10 3

output:

10
3
3

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 540ms
memory: 3796kb

input:

3051 198219
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...

output:

78
78
70
64
60
55
60
58
52
54
51
53
56
51
51
57
55
52
49
55
49
50
53
49
49
48
49
48
53
50
50
54
47
52
45
49
49
46
47
48
49
50
48
49
47
48
47
49
48
50
48
49
48
47
49
48
51
48
48
45
45
46
50
50
50
48
49
46
47
47
46
48
48
47
49
47
46
47
46
47
46
45
47
49
49
50
51
48
48
49
47
47
48
50
46
47
48
50
46
47
...

result:

ok 13214 lines

Test #4:

score: -100
Time Limit Exceeded

input:

6173 198631
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 99 ...

output:


result: