有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
第一行N，M
接下来M行，每行形如1 a b c或2 a b c
题解
不得不承认我真是太弱了，怼了这题几天，最后一个点还特判过的。。
不过终于解决这道难题，收货颇丰【QAQ蒟蒻的自我安慰】
首先说一下最容易想到的树套树做法
要求第k大，我们先权值取反，变为求第k小
先建一棵树维护每个权值出现的次数，这棵树并不是真的存在，它储存的只是另一棵树的根节点，对于根节点建一棵关于区间的线段树，表示权值[a,b]在区间[l,r]出现的次数
这样我们就可以通过二分求出[l,r]区间内的第k小数
例如我们要求[1,10]内第5小的数【假设总权值为[1,100]】
我们现在权值[1,50]的区间的根节点所在线段树询问[1,10]内的值，表示[1,50]权值在[1,10]这个区间内出现过多少次，
如果大于5，说明[1,10]区间内第k小一定在[1,50]权值内，
同理，我们在[1,25]找，一直到区间长度为1，即为答案
修改就更简单了，找到对应区间的树进行区间修改就好了
但正解不是树套树
正解是 整体二分 + 线段树
我们按顺序先存下所有的询问与修改，然后以权值为关键字进行二分，建立一棵关于区间出现次数的线段树
每次我们将一半的权值添加对线段树进行修改，就可以的出当前任意区间内该部分权值出现的次数，就可以对所有的询问进行二分了
对于区间[l,r]，我们找到中间的mid值，然后从左开始扫描操作
1、如果是修改 且 权值大于mid，那么属于[mid + 1,r]范围内的权值，在线段树中[a,b]区间整体+1，表示[mid + 1,r]在区间[a,b]个出现了一次，然后放到相应的左边右边
2、如果是询问，我们看看当前[a,b]区间[mid + 1,r]权值出现的次数，如果大于c，说明在答案在该区间内，放到右边，否则放到左边
3、所有处理完后，对左右区间再二分，直至区间长度为1，得到答案
下面是树套树【没有A】
#include
#include
#include
#include
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 400005,maxm = 20000005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1;char c = getchar();
while (c <48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}
return out * flag;
}
int a,b,c,N;
int n,m,siz = 0;
int rt[maxn];
int ls[maxm],rs[maxm],sum[maxm],lazy[maxm],L,R;
inline void pd(int u,int l,int r){
if (!lazy[u] || l == r) return;
if (!ls[u]) ls[u] = ++siz;
if (!rs[u]) rs[u] = ++siz;
lazy[ls[u]] += lazy[u]; lazy[rs[u]] += lazy[u];
int mid = l + r >> 1;
sum[ls[u]] += lazy[u] * (mid - l + 1);
sum[rs[u]] += lazy[u] * (r - mid);
lazy[u] = 0;
}
void modify(int& u,int l,int r){
if (!u) u = ++siz;
if (l >= L && r <= R){
sum[u] += (r - l + 1);
lazy[u]++;
}else {
pd(u,l,r);
int mid = l + r >> 1;
if (mid >= L) modify(ls[u],l,mid);
if (mid = L && r <= R) return sum[u];
else {
pd(u,l,r);
int mid = l + r >> 1;
if (mid >= R) return Query(ls[u],l,mid);
else if (mid > 1;
modify(rt[u],1,n);
if (c <= mid) r = mid,u = u <<1;
else l = mid + 1,u = u <<1 | 1;
}
modify(rt[u],1,n);
}
inline void solve(){
int u = 1,l = 1,r = N,t;
L = a; R = b;
while (l > 1;
t = Query(rt[u <<1],1,n);
if (c <= t) r = mid,u = u <<1;
else l = mid + 1,u = u <<1 | 1,c -= t;
}
printf("%d\n",N - l + 1 - n);
}
int main()
{
int cmd;
n = read(); m = read();N = n * 2 + 1;
while (m--){
cmd = read(); a = read(); b = read(); c = read();
if (cmd & 1){
c += n;
c = N - c + 1;
insert();
}else solve();
}
return 0;
}
正解，整体二分【特判了一下。。。】
#include
#include
#include
#include
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 500005,maxm = 100005,INF = 1000000000;
//begin 18:00 end 19:27
inline int read(){
int out = 0,flag = 1;char c = getchar();
while (c <48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}
return out * flag;
}
int n,M;
struct node{
int l,r,v,p,id,k;
}e[maxn];
inline bool cmp(const node& a,const node& b){
return a.k == b.k ? a.id > 1;
sum[u<<1] += (mid - l + 1) * lazy[u];
sum[u<<1|1] += (r - mid) * lazy[u];
lazy[u<<1] += lazy[u];
lazy[u<<1|1] += lazy[u];
lazy[u] = 0;
}
}
inline void update(int u,int l,int r){
pd(u,l,r);
if (l >= L && r <= R){
sum[u] += (r - l + 1);
lazy[u]++;
}
else {
int mid = l + r >> 1;
if (mid >= L) update(u<<1,l,mid);
if (mid = L && r <= R) return sum[u];
else {
int mid = l + r >> 1;
if (mid >= R) return Query(u<<1,l,mid);
else if (mid er) return;
if (l == r){
for (int i = el; i <= er; i++)
if (e[i].p == 2) ans[e[i].id] = l;
}
else {
cl[1] = true; sum[1] = lazy[1] = 0;
int mid = (l + r) >> 1,i = el - 1,t;
for (int k = el; k <= er; k++){
if (e[k].p == 1){
if (e[k].v > mid){
L = e[k].l; R = e[k].r;
update(1,1,n);
e[k].k = 1;
}else {
e[k].k = 0;
i++;
}
}
else {
L = e[k].l; R = e[k].r;
t = Query(1,1,n);
if (e[k].v <= t) e[k].k = 1;
else {
e[k].v -= t;
e[k].k = 0;
i++;
}
}
}
sort(e + el,e + er + 1,cmp);
solve(l,mid,el,i);
solve(mid + 1,r,i + 1,er);
}
}
void init(){
n = read(); M = read();
REP(i,M){
e[i].p = read();
e[i].l = read();
e[i].r = read();
e[i].v = read();
if (e[i].p == 1) e[i].v = e[i].v + n;
e[i].id = i;
}
memset(ans,-1,sizeof(ans));
}
void print(){
for (int i = 1; i <= M; i++)
if (ans[i] != -1) {
if (ans[i] == n) printf("50000\n");
else printf("%d\n",ans[i] - n);
}
}
int main()
{
init();
solve(0,2 * n,1,M);
print();
return 0;
}
京公网安备 11010802041100号