题目链接：传送门

Description

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

Input

第一行N，M接下来M行，每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3

Sample Output

1 2 1

Solution

这道题调了好久，最后发现(mid - l + 1)打成(l - mid + 1)了。。。 又是一道树套树的题 外层是权值线段树，内层是区间线段树维护标记 对权值建一颗权值线段树 其中的某个点表示权值在某个范围的数的个数 然后每个点上建一颗区间线段树 表示该点表示的权值范围内位于原数组的某个区间的数的个数

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
const int Maxn = 50000 + 100;
struct node
{
    int lson, rson;
    LL mark, Sum;
}Tree[Maxn * 400];
int root[Maxn * 8];
int Cnt;
int N, M;
inline void push_down(int x, int l, int r)
{
    if (!Tree[x].mark) return ;
    int mid = (l + r) >> 1;
    if (!Tree[x].lson) Tree[x].lson = ++Cnt;
    if (!Tree[x].rson) Tree[x].rson = ++Cnt;
    Tree[Tree[x].lson].mark += Tree[x].mark;
    Tree[Tree[x].rson].mark += Tree[x].mark;
    Tree[Tree[x].lson].Sum += Tree[x].mark * (LL)(mid - l + 1);
    Tree[Tree[x].rson].Sum += Tree[x].mark * (LL)(r - mid);
    Tree[x].mark = 0;
}
inline void push_up(int x)
{
    Tree[x].Sum = Tree[Tree[x].lson].Sum + Tree[Tree[x].rson].Sum;
}
inline void add2(int &R, int l, int r, int x, int y)
{
    if (!R) R = ++Cnt;
    if (x == l && y == r)
    {
        Tree[R].Sum += (y - x + 1);
        Tree[R].mark ++;
        return ;
    }
    push_down(R, l, r);
    int mid = (l + r) >> 1;
    if (y <= mid) add2(Tree[R].lson, l, mid, x, y);
    else if ( x > mid) add2(Tree[R].rson, mid + 1, r, x, y);
    else add2(Tree[R].lson, l, mid, x, mid), add2(Tree[R].rson, mid + 1, r, mid + 1, y);
    push_up(R);
}
inline void add1 (int R, int l, int r, int x, int y, int z)
{
    add2(root[R], 1, N, x, y);
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (z <= mid) add1(R << 1, l, mid, x, y, z);
    else add1(R << 1 | 1, mid + 1, r, x, y, z);
}
inline LL query2(int R, int l, int r, int x, int y)
{
    if (!R) return 0;
    if (l == x && r == y)
        return Tree[R].Sum;
    push_down(R, l, r);
    int mid = (l + r) >> 1;
    if (y <= mid) return query2(Tree[R].lson, l, mid, x, y);
    else if (x > mid) return query2(Tree[R].rson, mid + 1, r, x, y);
    else return query2(Tree[R].lson, l, mid, x, mid) + query2(Tree[R].rson, mid + 1, r, mid + 1, y);
}
inline int query1(int R, int l, int r, int x, int y, LL z)
{
    if (l == r)
        return l;
    int mid = (l + r) >> 1;
    LL t = query2(root[R << 1 | 1], 1, N, x, y);
    if (z <= t) return query1(R << 1 | 1, mid + 1, r, x, y, z);
    else return query1(R << 1, l, mid, x, y, z - t);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= M; ++i)
    {
        int type, x, y, z;
        scanf("%d%d%d%d", &type, &x, &y, &z);
        LL z1 = (LL)z;
        if (type == 1)
            add1(1, 1, N, x, y, z);
        else printf("%d\n", query1(1, 1, N, x, y, z1));
    }
    return 0;
}