蒟蒻 0 分求助
查看原帖
蒟蒻 0 分求助
450290
MurataHimeko楼主2021/2/27 10:44

求助大佬

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;

inline int read () {
	register int x(0), f(1);
	char ch = getchar ();
	while (ch < '0' || ch > '9') {if (ch == '-') f = ~f+1; ch = getchar ();}
	while (ch <= '9' && ch >= '0') {x = (x<<3) + (x<<1) + (ch^48); ch = getchar ();}
	return x * f;
}

int n, m;

struct node {
	int l, r;
	int laz;
	int qwq;
	int pre;
	int suf;
}e[200005];

void build (int o, int l, int r) {
	e[o].l = l, e[o].r = r;
	e[o].qwq = e[o].pre = e[o].suf = r - l + 1;
	if (l == r) return ;
	int mid = l + r >> 1;
	build (o<<1, l, mid);
	build (o<<1|1, mid+1, r);
}

void pushdown (int o) {
	if (e[o].laz == 1) {
		e[o<<1].laz = e[o<<1|1].laz = 1;
		int len = e[o].r - e[o].l + 1;
		e[o<<1].qwq = e[o<<1].suf = e[o<<1].pre = len - (len >> 1);
		e[o<<1|1].qwq = e[o<<1|1].suf = e[o<<1|1].pre = len>>1;
		e[o].laz = 0;
	}
	if (e[o].laz == 2) {
		e[o<<1].laz = e[o<<1|1].laz = 2;
		e[o<<1].qwq = e[o<<1].pre = e[o<<1].suf = e[o<<1|1].qwq = e[o<<1|1].suf = e[o<<1|1].pre = 0;
		e[o].laz = 0;
	}
} 

int access (int o, int limit) {
	pushdown (o);
	if (e[o].l == e[o].r) return e[o].l;
	int mid = e[o].l + e[o].r >> 1;
	if (e[o<<1].qwq >= limit) return access (o<<1, limit);
	if (e[o<<1].suf + e[o<<1|1].pre >= limit) return mid - e[o<<1].suf + 1;
	else return access (o<<1|1, limit);
}

void revise (int o, int flag, int l, int r) {
	if (l <= e[o].l && e[o].r <= r) {
		e[o].laz = flag;
		if (flag == 1) e[o].qwq = e[o].pre = e[o].suf = e[o].r - e[o].l + 1;
		else e[o].qwq = e[o].pre = e[o].suf = 0;
		return ;
	}
	pushdown (o);
	int mid = e[o].l + e[o].r >> 1;
	if (l <= mid) revise (o<<1, flag, l, r);
	if (r > mid) revise (o<<1|1, flag, l, r);
	if (e[o<<1].pre == e[o<<1].qwq) e[o].pre = e[o<<1].qwq + e[o<<1|1].pre;
	else e[o].pre = e[o<<1].pre;
	if (e[o<<1|1].suf = e[o<<1|1].qwq) e[o].suf = e[o<<1|1].qwq + e[o<<1].suf;
	else e[o].suf = e[o<<1|1].suf;
	e[o].qwq = max (e[o<<1].qwq, max (e[o<<1|1].qwq, e[o<<1].suf + e[o<<1|1].pre));
}

int main () {
	n = read (), m = read ();
	build (1, 1, n);
	while (m--) {
		int flag = read ();
		if (flag == 1) {
			int x = read ();
			if (e[1].qwq >= x) {
				int tmp = access (1, x);
				revise (1, 2, tmp, tmp + x - 1); 
				printf("%d\n" ,tmp);
			}
			else puts ("0");
		}
		else {
			int x = read (), y = read ();
			revise (1, 1, x, x + y - 1);
		}
	}
}
2021/2/27 10:44
加载中...