作者:Ailsa大宝贝 | 来源:互联网 | 2023-05-17 17:45
题意
n个数,m次操作,每次询问区间第k大,或者给区间加上一个数。
$数据范围:1 ≤ n,m ≤ 10^5 ,1 ≤ k ≤ 10。$
题解
由于k很小,直接在线段树内维护,前k大的数。
code
1 #include
2 #include
3
4 #define lson l,m,rt<<1
5 #define rson m+1,r,rt<<1|1
6
7 #define N 100010
8 #define K 10
9
10 int n,m;
11 struct Tree {
12 int data[K];
13 Tree() {memset(data,0,sizeof(data));}
14 Tree operator + (const Tree &a) const {
15 Tree ret;
16 int p1 = 0,p2 = 0;
17 for (int i=0; ii)
18 if (data[p1] > a.data[p2]) ret.data[i] = data[p1++
];
19 else ret.data[i] = a.data[p2++
];
20 return ret;
21 }
22 }t[N<<
2];
23 int a[N],tag[N<<
2];
24 25 inline
int read() {
26 int x =
0,f =
1;
char ch =
getchar();
27 for (; ch<
'0'||ch>
'9'; ch =
getchar())
28 if (ch==
'-') f = -
1;
29 for (; ch>=
'0'&&ch<=
'9'; ch =
getchar())
30 x = x*
10+ch-
'0';
31 return x*
f;
32 }
33 34 inline
void pushup(
int rt) {
35 t[rt] = t[rt<<
1] + t[rt<<
1|
1];
36 }
37 inline
void pushdown(
int rt) {
38 if (tag[rt]) {
39 tag[rt<<
1] +=
tag[rt];
40 for (
int i=
0; i
i)
41 if (t[rt<<1].data[i]) t[rt<<1].data[i] += tag[rt];//只加有的数字
42 tag[rt<<1|1] += tag[rt];
43 for (int i=0; ii)
44 if (t[rt<<1|1].data[i]) t[rt<<1|1].data[i] += tag[rt];
45 tag[rt] = 0;
46 }
47 }
48 void build(int l,int r,int rt) {
49 if (l==r) {
50 t[rt].data[0] = a[l];
51 return ;
52 }
53 int m = (l+r) >> 1;
54 build (lson);
55 build (rson);
56 pushup(rt);
57 }
58 void update(int l,int r,int rt,int L,int R,int c) {
59 if (L <= l && r <= R) {
60 tag[rt] += c;
61 for (int i=0; ii)
62 if (t[rt].data[i]) t[rt].data[i] += c;
63 return ;
64 }
65 pushdown(rt);
66 int m = (l+r) >> 1;
67 if (L <= m) update(lson,L,R,c);
68 if (R > m) update(rson,L,R,c);
69 pushup(rt);
70 }
71 Tree query(int l,int r,int rt,int L,int R) {
72 if (L <= l && r <= R) {
73 return t[rt];
74 }
75 pushdown(rt);
76 Tree ret;
77 int m = (l+r) >> 1;
78 if (L <= m) ret = ret + query(lson,L,R);
79 if (R > m) ret = ret + query(rson,L,R);
80 return ret ;
81 }
82 int main() {
83
84 int n = read(),m = read();
85 for (int i=1; i<=n; ++i) a[i] = read();
86 build(1,n,1);
87 Tree ans;
88 while (m--) {
89 int opt = read(),l = read(),r = read(),k = read();
90 if (opt==0) {
91 if (r-l+1 "-1");
92 else {
93 ans = query(1,n,1,l,r);
94 printf("%d\n",ans.data[k-1]);
95 }
96 }
97 else update(1,n,1,l,r,k);
98 }
99 return 0;
100 }
by zhx p106 无题