P3332 [ZJOI2013]K大数查询[线段树,整体二分]

题目描述

有 $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

输出格式:

输出每个询问的结果

输入输出样例

输入样例#1:

1
2
3
4
5
6
2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

输出样例#1:

1
2
3
1
2
1

说明

【样例说明】

第一个操作 后位置 1 的数只有 1 , 位置 2 的数也只有 1 。 第二个操作 后位置 1

的数有 1 、 2 ,位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是

1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3

大的数是 1 。‍

$N,M<=50000$, $N,M<=50000$

$a<=b<=N$

1操作中$|c|<=N$

2操作中 $c<=Maxlongint$

题解

关于92分wa点4原因:没开long long, 因为$5^{10}$个位置,每个位置$5^{10}$个数,int会爆

整体二分+线段树
二分答案的值 -n到n

1.修改操作:设修改的值为x

$x \le mid$,放到左边,因为对目前答案不影响(因为之后求的是 $>mid$ 的数的个数)

$x>mid$,放到右边,用线段数进行修改,放在右边(对答案有贡献)

2.查询操作

先求所处区间内 $>mid$ 的数的个数,设为s

$k \le s$ ( $k$为该询问是求该区间内第$k$大的数),放右边(答案肯定$>=mid$)

$k>s$ k-=s,然后放左边(答案肯定$<mid$)

二分结束条件:

$l=r$,这个区间内的询问的答案就为 $l$了

$l>r$ 直接退出

线段树清空可以巧妙的打标记,而不是每次清空.

这种方法跑得还是很慢的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
inline int qmax(int &x,int y) {if (x<y) x=y;}
inline int qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!isdigit(s));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(isdigit(s)) {k=k*10+(s^48);s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=50000+2000;
int n,m;
struct node
{
int flag,a,b,c,id,flag2,ans;
} a[maxn];
long long t[maxn<<2];
int p[maxn<<2],bj[maxn<<2];
inline void down(int d,int l,int r)
{
if (l==r) return;
if (bj[d])
{
t[d<<1]=0;p[d<<1]=0;bj[d<<1]=1;
t[d<<1|1]=0;p[d<<1|1]=0;bj[d<<1|1]=1;
bj[d]=0;
}
if (p[d]==0) return;
int mid=(l+r)>>1;
t[d<<1]+=p[d]*(mid-l+1);p[d<<1]+=p[d];
t[d<<1|1]+=p[d]*(r-mid);p[d<<1|1]+=p[d];
p[d]=0;
}
void xg(int x,int y,int d,int l,int r)
{
if (x<=l&&r<=y)
{
t[d]+=(y-x+1);p[d]++;return;
}
down(d,l,r);
int mid=(l+r)>>1;
if (y<=mid) xg(x,y,d<<1,l,mid);
else if (x>mid) xg(x,y,d<<1|1,mid+1,r);
else xg(x,mid,d<<1,l,mid),xg(mid+1,y,d<<1|1,mid+1,r);
t[d]=t[d<<1]+t[d<<1|1];
}
long long qh(int x,int y,int d,int l,int r)
{
if (x<=l&&r<=y) return t[d];
down(d,l,r);int mid=(l+r)>>1;
if (y<=mid) return qh(x,y,d<<1,l,mid);
else if (x>mid) return qh(x,y,d<<1|1,mid+1,r);
else return qh(x,mid,d<<1,l,mid)+qh(mid+1,y,d<<1|1,mid+1,r);
}
bool cmp(node aa,node bb) {return aa.id<bb.id;}
bool CMP(node aa,node bb) {return aa.flag2<bb.flag2;}
inline void ef(int l,int r,int x,int y)
{
if (y<x) return;
if (l==r) {for (int i=x;i<=y;i++) a[i].ans=l;return;}//标记答案
t[1]=0;p[1]=0;bj[1]=1;//线段书情况,bj=1:子树没清空,pushdown的时候可以顺便清空
int mid=(l+r)>>1;
int L=0,R=y;
long long s;
for (int i=x;i<=y;i++)
{
if (a[i].flag==1)
{
if (a[i].c<=mid) a[i].id=++L; else
{
xg(a[i].a,a[i].b,1,1,n);a[i].id=++R;
}
} else
{
s=qh(a[i].a,a[i].b,1,1,n);
if (s>=a[i].c) a[i].id=++R; else a[i].c-=s,a[i].id=++L;
}
}
sort(a+x,a+y+1,cmp);//这样可以把放左边的和放右边的区分开
ef(l,mid,x,x+L-1);ef(mid+1,r,x+L,y);//往下分
}
main()
{
n=read();m=read();
for (int i=1;i<=m;i++){a[i].flag=read();a[i].a=read();a[i].b=read();a[i].c=read();a[i].flag2=i;}
ef(-n-1,n+1,1,m);
sort(a+1,a+m+1,CMP);
for (int i=1;i<=m;i++) if (a[i].flag==2) printf("%d\n",a[i].ans);
return 0;
}