本地运行没问题,怎么就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;
}