9分RE求条
查看原帖
9分RE求条
487383
imnoob楼主2025/1/27 21:26

本地运行没问题,怎么就RE了?

#include <bits/stdc++.h>
#define Code using
#define by namespace
#define zzx std
#define re endofadream
Code by zzx;
int n, m, cnt = 0, ans[50010];
struct query
{
	int type, l, r, id;
	long long c;
}a[50010], a1[50010], a2[50010];
vector<long long> s;
long long tot = 0, re[50010];
struct Stree_sum
{
	int d[200010], tag[200010];
	void build(int s, int t, int p)
	{
		if(s == t)
		{
			d[p] = 0;
			return;
		}
		int mid = ((s + t) >> 1);
		build(s, mid, p * 2);
		build(mid + 1, t, p * 2 + 1);
		d[p] = d[p * 2] + d[p * 2 + 1];
	}
	void update(int l, int r, int s, int t, int x, int p)
	{
		if(l <= s && t <= r)
		{
			d[p] += long(t - s + 1) * x;
			tag[p] += x;
			return;
		}
		int mid = ((s + t) >> 1);
		if(tag[p] && s != t)
		{
			d[p * 2] += tag[p] * (mid - s + 1);
			d[p * 2 + 1] += tag[p] * (t - mid);
			tag[p * 2] += tag[p];
			tag[p * 2 + 1] += tag[p];
			tag[p] = 0;
		}
		if(l <= mid)
		{
			update(l, r, s, mid, x, p * 2);
		}
		if(mid < r)
		{
			update(l, r, mid + 1, t, x, p * 2 + 1);
		}
		d[p] = d[p * 2] + d[p * 2 + 1];
	}
	int getsum(int l, int r, int s, int t, int p)
	{
		if(l <= s && t <= r)
		{
			return d[p];
		}
		int mid = ((s + t) >> 1);
		if(tag[p] && s != t)
		{
			d[p * 2] += tag[p] * (mid - s + 1);
			d[p * 2 + 1] += tag[p] * (t - mid);
			tag[p * 2] += tag[p];
			tag[p * 2 + 1] += tag[p];
			tag[p] = 0;
		}
		int res = 0;
		if(l <= mid)
		{
			res += getsum(l, r, s, mid, p * 2);
		}
		if(mid < r)
		{
			res += getsum(l, r, mid + 1, t, p * 2 + 1);
		}
		return res;
	}
}stree; // don't want to write segment tree so i ctrlc + ctrlv
void solve(long long L, long long R, int l, int r)
{
	if(L > R || l > r)
	{
		return;
	}
	if(L == R)
	{
		for(int i = l; i <= r; ++i)
		{
			if(a[i].type == 2)
			{
				ans[a[i].id] = re[L];
			}
		}
		return;
	}
	long long mid = (L + R) / 2;
	int cnt1 = 0, cnt2 = 0;
	for(int i = l; i <= r; ++i)
	{
		if(a[i].type == 1)
		{
			if(a[i].c > mid)
			{
				stree.update(a[i].l, a[i].r, 1, n, 1, 1);
				a2[++cnt2] = a[i];
			}
			else
			{
				a1[++cnt1] = a[i];
			}
		}
		else
		{
			int k = stree.getsum(a[i].l, a[i].r, 1, n, 1);
			//cout << a[i].id << ' ' <<a[i].l << ' ' << a[i].r << ' ' << a[i].c << ' ' << k << '\n';
			if(a[i].c <= k)
			{
				a2[++cnt2] = a[i];
			}
			else
			{
				a[i].c -= k;
				a1[++cnt1] = a[i];
			}
		}
	}
	for(int i = 1; i <= cnt1; ++i)
	{
		a[i + l - 1] = a1[i];
	}
	for(int i = 1; i <= cnt2; ++i)
	{
		a[i + l + cnt1 - 1] = a2[i];
		if(a[i].type == 1)
		{
			stree.update(a1[i].l, a1[i].r, 1, n, -1, 1);
		}
	}
	solve(L, mid, l, l + cnt1 - 1);
	solve(mid + 1, R, l + cnt1, r);
}
int main()
{
	cin >> n >> m;
	stree.build(1, n, 1);
	for(int i = 1; i <= m; ++i)
	{
		cin >> a[i].type >> a[i].l >> a[i].r >> a[i].c;
		if(a[i].type == 1)
		{
			s.push_back(a[i].c);
		}
	}
	sort(s.begin(), s.end());
	s.erase(unique(s.begin(), s.end()), s.end());
	tot = s.size();
	for(int i = 1; i <= m; ++i)
	{
		if(a[i].type == 1)
		{
			long long k = lower_bound(s.begin(), s.end(), a[i].c) - s.begin() + 1;
			re[k] = a[i].c;
			a[i].c = k;
		}
		else
		{
			a[i].id = ++cnt;
		}
	}
	solve(1ll, tot, 1, m);
	for(int i = 1; i <= cnt; ++i)
	{
		cout << ans[i] << '\n';
	}
	return 0;
} 
2025/1/27 21:26
加载中...