题意：戳这里
思路：可以用cdq分治（很明显这种模型妹纸分治法很解决）。。不过为了学习树套树特地写了一下。。
所谓的树套树也第一层(最外层)普通的维护的是一个node,而树套树维护的是一个数据结构（一棵树）。。
树套树一般可以解决2维模型。。1维的话也就是普通的数据结构了。
比如poi07 的mokia其实就是一个2为线段树，不够空间不够所以必须写成树套树。。
本题的话如把权值看成一维，本来位置看成1维，那么其实也是2维模型。
插入就等价于每次在一条x=c 横线的[a,b]之间每个位置都插入1遍
查询等价于求第k大的在哪条横线上。。
对于这一题的话，可以如下：
首先最外层维护的是权值构成的线段树，
而对于每个权值，又对应着一棵线段树，不过这个线段树是下标线段树
由于空间有限，所以有用到才动态分配内存。。
然后每次插入的话在最外层包括value=c的logn段里面都插入，
查询的每次二分，左边太小右边找，正好从外层线段树从上到下。。
时间复杂度O(mlog2n)
code：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#define M0(x) memset(x, 0, sizeof(x))
using namespace std;
#define lson lc[rt], l, m
#define rson rc[rt], m+1, r
const int N = , M = ;
int rt[N<<], sum[M], lc[M], rc[M], lz[M];
int n, m, L, R, cnt, c; inline void push_up(const int& rt){
sum[rt] = sum[lc[rt]] + sum[rc[rt]];
} inline void push_down(const int &rt, const int& l, const int &r){
if (lz[rt]){
if (!lc[rt]) lc[rt] = ++cnt;
if (!rc[rt]) rc[rt] = ++cnt;
sum[lc[rt]] += lz[rt] * ((r-l+)>>), sum[rc[rt]] += lz[rt] * ((r-l+)>>);
lz[lc[rt]] += lz[rt], lz[rc[rt]] += lz[rt];
lz[rt] = ;
}
} int query(const int& rt,const int& l, const int& r){
if (!rt) return ;
if (L <= l && r <= R) return sum[rt];
int m = (l + r) >> , tmp1 = , tmp2 = ;
push_down(rt, l, r);
if (L <= m) tmp1 = query(lson);
if (R > m) tmp2 = query(rson);
return tmp1 + tmp2 + (min(R, r) - max(l, L) + ) * lz[rt];
} int query(int k){
int l = , r = n, mid, cur = , tmp;
while (l <= r){
if (l == r) return l;
mid = (l + r) >> ;
tmp = query(rt[cur<<], , n);
if (tmp >= k) r = mid, cur <<= ;
else l = mid + , k -= tmp, cur = cur<<|;
}
return l;
} void update(int &rt,const int& l,const int& r){
if (!rt) rt = ++cnt;
if (L <= l && r <= R){
sum[rt] += (r - l + ), ++lz[rt];
return;
}
int m = (l + r) >> ;
push_down(rt, l, r);
if (L <= m) update(lson);
if (R > m) update(rson);
push_up(rt);
} void insert(const int& c){
int l = , r = n, cur = , mid;
while (l <= r){
update(rt[cur], , n);
if (l == r) break;
mid = (l + r) >> ;
if (c <= mid) cur<<= , r = mid;
else l = mid + , cur = cur<<|;
}
} void solve(){
cnt = ;
int op;
while (m--){
scanf("%d%d%d%d", &op, &L, &R, &c);
if (op==) c = n - c + , insert(c);
else printf("%d\n", n - query(c) + );
}
} int main(){
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
while (scanf("%d%d", &n, &m) != EOF){
solve();
}
return ;
}
code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#define M0(x) memset(x, 0, sizeof(x))
using namespace std;
#define lson lc[rt], l, m
#define rson rc[rt], m+1, r
const int N = , M = ;
int rt[N<<], sum[M], lc[M], rc[M], lz[M];
int n, m, L, R, cnt, c; int query(const int& rt,const int& l, const int& r){
if (!rt) return ;
if (L <= l && r <= R) return sum[rt];
int m = (l + r) >> , tmp1 = , tmp2 = ;
if (L <= m) tmp1 = query(lson);
if (R > m) tmp2 = query(rson);
return tmp1 + tmp2 + (min(R, r) - max(l, L) + ) * lz[rt];
} int query(int k){
int l = , r = n, mid, cur = , tmp;
while (l <= r){
if (l == r) return l;
mid = (l + r) >> , tmp = query(rt[cur<<], , n);
if (tmp >= k) r = mid, cur <<= ;
else l = mid + , k -= tmp, cur = cur<<|;
}
return l;
} void update(int &rt,const int& l,const int& r){
if (!rt) rt = ++cnt;
if (L <= l && r <= R){
sum[rt] += (r - l + ), ++lz[rt];
return;
}
int m = (l + r) >> ;
if (L <= m) update(lson);
if (R > m) update(rson);
sum[rt] = sum[lc[rt]] + sum[rc[rt]] + lz[rt] * (r - l + );
} void insert(const int& c){
int l = , r = n, cur = , mid;
while (l <= r){
update(rt[cur], , n);
if (l == r) break;
mid = (l + r) >> ;
if (c <= mid) cur<<= , r = mid;
else l = mid + , cur = cur<<|;
}
} void solve(){
cnt = ;
int op;
while (m--){
scanf("%d%d%d%d", &op, &L, &R, &c);
if (op==) c = n - c + , insert(c);
else printf("%d\n", n - query(c) + );
}
} int main(){
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
while (scanf("%d%d", &n, &m) != EOF){
solve();
}
return ;
}
第一个lazy直接下放慢成狗。。学习了一下优美姿势快了不少。。
