刚学OI一普朗克时间,遭遇灵异事件,拼全力无法战胜
查看原帖
刚学OI一普朗克时间,遭遇灵异事件,拼全力无法战胜
500542
lvyongfeng楼主2025/8/30 21:36

如题,我莫名其妙全部TLE了,但是时间复杂度没有问题,校内oj通过,校内oj用的Linux系统,因此题为省选题,所以我认为测试数据相同,我用从校内oj上捞了几组数据,本地测试通过

#include<bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs ((u << 1) | 1)
using namespace std;

int read() {
    int sign = 1, cnt = 0;
	char c = getchar();
	while(!isdigit(c)) {
		if(c == '-') {
			sign = -1;
			c = getchar();
		}
	}
	while(isdigit(c)) {
		cnt = cnt * 10 + (c ^ 48);
		c = getchar();
	}
	return cnt * sign;
}

const int N = 1e5 + 10;
int a[N];
namespace tree{
	struct node{
		int l, r;
		int maxn[2], lmaxn[2], rmaxn[2];
		int sum, tag, rev;
	}tr[N << 2];
	
	void push_up(int u){
		tr[u].sum = tr[ls].sum + tr[rs].sum;
		tr[u].lmaxn[0] = tr[ls].lmaxn[0];
		tr[u].lmaxn[1] = tr[ls].lmaxn[1];
		if(tr[ls].lmaxn[0] == tr[ls].r - tr[ls].l + 1){
			tr[u].lmaxn[0] += tr[rs].lmaxn[0];
		}
		if(tr[ls].lmaxn[1] == tr[ls].r - tr[ls].l + 1){
			tr[u].lmaxn[1] += tr[rs].lmaxn[1];
		}
		tr[u].rmaxn[0] = tr[rs].rmaxn[0];
		tr[u].rmaxn[1] = tr[rs].rmaxn[1];
		if(tr[rs].rmaxn[0] == tr[rs].r - tr[rs].l + 1){
			tr[u].rmaxn[0] += tr[ls].rmaxn[0];
		}
		if(tr[rs].rmaxn[1] == tr[rs].r - tr[rs].l + 1){
			tr[u].rmaxn[1] += tr[ls].rmaxn[1];
		}
		tr[u].maxn[0] = max(max(tr[ls].maxn[0], tr[rs].maxn[0]), tr[ls].rmaxn[0] + tr[rs].lmaxn[0]);
		tr[u].maxn[1] = max(max(tr[ls].maxn[1], tr[rs].maxn[1]), tr[ls].rmaxn[1] + tr[rs].lmaxn[1]);
	}
	
	void main_swap(int u){
		swap(tr[u].maxn[1], tr[u].maxn[0]);
		swap(tr[u].lmaxn[1], tr[u].lmaxn[0]);
		swap(tr[u].rmaxn[1], tr[u].rmaxn[0]);
	}
	
	void addtag_turn(int u, int x){
		tr[u].sum = (tr[u].r - tr[u].l + 1) * x;
		tr[u].tag = x;
		tr[u].rev = 0;
		tr[u].maxn[x] = tr[u].lmaxn[x] = tr[u].rmaxn[x] = tr[u].r - tr[u].l + 1;
		tr[u].maxn[!x] = tr[u].lmaxn[!x] = tr[u].rmaxn[!x] = 0;
	}
	
	void addtag_reverse(int u){
		tr[u].sum = (tr[u].r - tr[u].l + 1) - tr[u].sum;
		if(tr[u].tag != -1)	tr[u].tag ^= 1;
		else	tr[u].rev ^= 1;
		main_swap(u);
	}
	
	void push_down(int u){
		if(tr[u].l == tr[u].r)	return;
		if(tr[u].tag != -1){
			addtag_turn(ls, tr[u].tag);
			addtag_turn(rs, tr[u].tag);
			tr[u].tag = -1;
		}
		if(tr[u].rev){
			addtag_reverse(ls);
			addtag_reverse(rs);
			tr[u].rev = 0;
		}
	}
	
	void build(int u, int l, int r){
		tr[u].l = l, tr[u].r = r;
		tr[u].tag = -1;
		tr[u].rev = 0;
		if(l == r){
			tr[u].sum = a[l];
			tr[u].maxn[0] = tr[u].lmaxn[0] = tr[u].rmaxn[0] = (a[l] == 0) ? 1 : 0;
			tr[u].maxn[1] = tr[u].lmaxn[1] = tr[u].rmaxn[1] = (a[l] == 1) ? 1 : 0;
			return;
		}
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
		push_up(u);
	}
	
	void update_turn(int u, int ql, int qr, int x){
		if(tr[u].l >= ql && tr[u].r <= qr){
			addtag_turn(u, x);
			return;
		}
		push_down(u);
		int mid = (tr[u].l + tr[u].r) >> 1;
		if(mid >= ql)	update_turn(ls, ql, qr, x);
		if(mid < qr)	 update_turn(rs, ql, qr, x);
		push_up(u);
	}
	
	void update_reverse(int u, int ql, int qr){
		if(tr[u].l >= ql && tr[u].r <= qr){
			addtag_reverse(u);
			return;
		}
		push_down(u);
		int mid = (tr[u].l + tr[u].r) >> 1;
		if(mid >= ql)	update_reverse(ls, ql, qr);
		if(mid < qr)	 update_reverse(rs, ql, qr);
		push_up(u);
	}
	
	int query_sum(int u, int ql, int qr){
		if(tr[u].l >= ql && tr[u].r <= qr){
			return tr[u].sum;
		}
		push_down(u);
		int mid = (tr[u].l + tr[u].r) >> 1, ans = 0;
		if(mid >= ql)	ans += query_sum(ls, ql, qr);
		if(mid < qr)	 ans += query_sum(rs, ql, qr);
		return ans;
	}
	
	int query_maxn(int u, int ql, int qr){
		if(tr[u].l >= ql && tr[u].r <= qr){
			return tr[u].maxn[1];
		}
		push_down(u);
		int mid = (tr[u].l + tr[u].r) >> 1;
		if(qr <= mid)	return query_maxn(ls, ql, qr);
		if(ql > mid)	 return query_maxn(rs, ql, qr);
		
		int left = query_maxn(ls, ql, mid);
		int right = query_maxn(rs, mid + 1, qr);
		int cross = min(tr[ls].rmaxn[1], mid - ql + 1) + min(tr[rs].lmaxn[1], qr - mid);
		return max({left, right, cross});
	}
}

int main() {
//	freopen("1858_7.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	int n = read(), T = read();
	for(int i = 1; i <= n; i++){
		a[i] = read();
	}
	tree::build(1, 1, n);
	while(T--){
		int opt = read(), l = read(), r = read();
		l++, r++;
		switch(opt){
			case 0: tree::update_turn(1, l, r, 0); break;
			case 1: tree::update_turn(1, l, r, 1); break;
			case 2: tree::update_reverse(1, l, r); break;
			case 3: printf("%d\n", tree::query_sum(1, l, r)); break;
			case 4: printf("%d\n", tree::query_maxn(1, l, r)); break;
		}
	}
	return 0;
}

附上校内oj评测截图

蒟蒻已经快疯了。。。求调玄关。。。

2025/8/30 21:36
加载中...