[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=3110
[算法]
整体二分 + 线段树
时间复杂度 : O(NlogN ^ 2)
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500010
typedef long long ll;
typedef long double ld; struct query
{
int type , a , b;
ll c;
int id;
} q[MAXN]; int n , m;
int ans[MAXN]; struct Segment_Tree
{
ll cnt[MAXN << ] , tag[MAXN << ];
Segment_Tree()
{
memset(cnt , , sizeof(cnt));
}
inline void pushdown(int index , int l , int r)
{
int mid = (l + r) >> ;
cnt[index << ] += (mid - l + ) * tag[index];
cnt[index << | ] += (r - mid) * tag[index];
tag[index << ] += tag[index];
tag[index << | ] += tag[index];
tag[index] = ;
}
inline void update(int index)
{
cnt[index] = cnt[index << ] + cnt[index << | ];
}
inline void modify(int now , int l , int r , int ql , int qr , int value)
{
if (l == ql && r == qr)
{
cnt[now] += 1ll * value * (qr - ql + );
tag[now] += 1ll * value;
return;
}
pushdown(now , l , r);
int mid = (l + r) >> ;
if (mid >= qr) modify(now << , l , mid , ql , qr , value);
else if (mid + <= ql) modify(now << | , mid + , r , ql , qr , value);
else
{
modify(now << , l , mid , ql , mid , value);
modify(now << | , mid + , r , mid + , qr , value);
}
update(now);
}
inline ll query(int now , int l , int r , int ql , int qr)
{
if (l == ql && r == qr)
return cnt[now];
pushdown(now , l , r);
int mid = (l + r) >> ;
if (mid >= qr) return query(now << , l , mid , ql , qr);
else if (mid + <= ql) return query(now << | , mid + , r , ql , qr);
else return query(now << , l , mid , ql , mid) + query(now << | , mid + , r , mid + , qr);
}
} SGT;
template <typename T> inline void chkmin(T &x , T y) { x = min(x , y); }
template <typename T> inline void chkmax(T &x , T y) { x = max(x , y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
inline void divide(int l , int r , int L , int R)
{
static query tl[MAXN] , tr[MAXN];
int mid = (l + r) >> ;
if (L > R) return;
if (l == r)
{
for (int i = L; i <= R; i++)
if (q[i].type == ) ans[q[i].id] = mid;
return;
} else
{
int pl = , pr = ;
for (int i = L; i <= R; i++)
{
if (q[i].type == )
{
if (q[i].c > mid)
{
tr[++pr] = q[i];
SGT.modify( , , n , q[i].a , q[i].b , );
} else tl[++pl] = q[i];
} else
{
if (SGT.query( , , n , q[i].a , q[i].b) >= q[i].c)
tr[++pr] = q[i];
else
{
q[i].c -= SGT.query( , , n , q[i].a , q[i].b);
tl[++pl] = q[i];
}
}
}
for (int i = L; i <= R; i++)
if (q[i].type == && q[i].c > mid) SGT.modify( , , n , q[i].a , q[i].b , -);
for (int i = L; i <= L + pl - ; i++) q[i] = tl[i - L + ];
for (int i = L + pl; i <= R; i++) q[i] = tr[i - L - pl + ];
divide(l , mid , L , L + pl - );
divide(mid + , r , L + pl , R);
}
} int main()
{ read(n); read(m);
vector< int > que;
for (int i = ; i <= m; i++)
{
read(q[i].type);
read(q[i].a);
read(q[i].b);
read(q[i].c);
q[i].id = i;
if (q[i].type == ) que.push_back(i);
}
divide(-n , n , , m);
for (unsigned i = ; i < que.size(); i++) printf("%d\n" , ans[que[i]]); return ;
}