题解当复习笔记…
算法1
(整体二分 + 线段树) $O(n*log^2n)$
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define dbgfull(x) cerr << #x << " = " << x << " (line " << __LINE__ << ")"<<endl;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(x) cerr << #x " = " << (x) << endl
#define endl "\n"
#define int long long
#define PI acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e5+5,M = N * 2;
int mod = 1e9 +7;
int n,m,k,S,T;
struct node{
int l,r,sum,add;
}tr[N * 4];
void build(int u,int l,int r){
tr[u] = {l,r};
if(l == r) return;
int mid = l + r >> 1;
build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
}
void pushup(int u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u){
node &rt = tr[u],&l = tr[u << 1],&r = tr[u << 1 | 1];
if(rt.add){
l.add += rt.add,l.sum += rt.add * (l.r - l.l + 1);
r.add += rt.add,r.sum += rt.add * (r.r - r.l + 1);
rt.add = 0;
}
}
void modify(int u,int l,int r,int x){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].add += x;
tr[u].sum += x * (tr[u].r - tr[u].l + 1);
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1,l,r,x);
if(r > mid) modify(u << 1 | 1,l,r,x);
pushup(u);
}
int query(int u,int l,int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if(l <= mid) res += query(u << 1,l,r);
if(r > mid) res += query(u << 1 | 1,l,r);
return res;
}
struct Query{
int op,l,r,x,id;
}q[N],lq[N],rq[N];
int ans[N];
void work(int l,int r,int ql,int qr){
if(l > r || ql > qr) return;
if(l == r){
for(int i = ql ; i <= qr ; ++i){
if(q[i].op == 2) ans[q[i].id] = l;
}
return;
}
int mid = l + r >> 1,nl = 0,nr = 0;
for(int i = ql ; i <= qr ; ++i){
//插入操作
if(q[i].op == 1){
if(q[i].x <= mid) modify(1,q[i].l,q[i].r,1),lq[nl++] = q[i];
else rq[nr++] = q[i];
}
//查询操作
else{
//查询在查询区间中小于mid的个数
int t = query(1,q[i].l,q[i].r);
//若个数大于x则表示第x大数小于等于mid,去左区间查询
if(t >= q[i].x) lq[nl++] = q[i];
//否则表示第x大数大于 mid,去右区间查询,并将排名减去左区间的个数
else{
q[i].x -= t;
rq[nr++] = q[i];
}
}
}
//回溯线段树
for(int i = ql ; i <= qr ; ++i){
if(q[i].op == 1){
if(q[i].x <= mid) modify(1,q[i].l,q[i].r,-1);
}
}
for(int i = 0 ; i < nl ; ++i) q[ql + i] = lq[i];
for(int i = 0 ; i < nr ; ++i) q[ql + nl + i] = rq[i];
work(l,mid,ql,ql + nl - 1);
work(mid + 1,r,ql + nl,qr);
}
void solve(){
cin >> n >> m;
build(1,1,n);
int nq = 0;
for(int i = 1 ; i <= m ; ++i){
int op,l,r,x;
cin >> op >> l >> r >> x;
//小技巧(大概:插入时存-x,查询第x小数更方便
if(op == 1) q[i] = {op,l,r,-x};
else q[i] = {op,l,r,x,++nq};
}
work(-n,n,1,m);
for(int i = 1 ; i <= nq ; ++i) cout << -ans[i] << endl;
}
signed main(){
IOS;
solve();
return 0;
}
/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/