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

HINT



【样例说明】

第一个操作 后位置 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操作中abs(c)<=N

2操作中abs(c)<=Maxlongint



一道树套树的题

外层是一颗权值线段树

内层是传统的区间线段树

插入：在a-b插入权值c 

在外层线段树所有包含权值c的线段中，在其里层的线段树插入线段a-b

询问：在a-b中询问第k大的权值

从外层线段树（权值）开始，如果右孩子的内层线段树在区间a-b中的计数超过k个，显然答案在右孩子，否则在左孩子，以此类推


代码：

</pre><pre name="code" class="cpp">#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
struct Tree
{
	int l,r,lazy,sum;
}t[20000010];
int root[200010];
int n,m,sz,a,b,c;

inline int ReadInt();//输入优化 
void push_down(int k, int l, int r);
int query(int k, int l, int r, int a, int b);
void modify(int &k ,int l, int r, int a, int b);
void insert();
int solve();

int main()
{
	n = ReadInt();
	m = ReadInt();
	for(int Z = 1; Z <= m; Z ++)
	{
		int f = ReadInt();
		a = ReadInt();
		b = ReadInt();
		c = ReadInt();
		if(f == 1)
		{
			c = n - c + 1;
			insert();
		}
		else
			printf("%d\n",n - solve() + 1);
	}
	
	return 0;
}

inline int ReadInt()
{
    int x = 0,f = 1;
	char ch = getchar();
    while(ch < '0' || ch > '9')
	{
		if(ch == '-')f =- 1;
		ch=getchar();
	}
    while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
    return x * f;
} 

void push_down(int k, int l, int r)
{
	if(!t[k].lazy || l == r) return;
	if(!t[k].l) sz ++, t[k].l = sz;
	if(!t[k].r) sz ++, t[k].r = sz;
	t[ t[k].l ].lazy += t[k].lazy;
	t[ t[k].r ].lazy += t[k].lazy;
	int mid = (l + r) >> 1;
	t[ t[k].l ].sum = (mid - l + 1) * t[k].lazy;
	t[ t[k].r ].sum = (r - mid) * t[k].lazy;
	t[k].lazy = 0;
}

int query(int k, int l, int r, int a, int b)
{
	if(!k) return 0;
	push_down(k,l,r);
	if(l == a && r == b) return t[k].sum;
	int mid = (l + r) >> 1;
	if(b <= mid) return query(t[k].l, l, mid, a, b);
	else if(a > mid) return query(t[k].r, mid + 1, r, a, b);
	else return query(t[k].l, l, mid, a, mid) + query(t[k].r, mid + 1, r, mid + 1, b);
}

void modify(int &k ,int l, int r, int a, int b)
{
	if(!k) sz ++, k = sz;
	push_down(k,l,r);
	if(l == a && r == b)
	{
		t[k].sum += r - l + 1;
		t[k].lazy ++;
		return;
	}
	int mid = (l + r) >> 1;
    if(b <= mid) modify(t[k].l, l, mid, a, b);
	else if(a > mid) modify(t[k].r, mid + 1, r, a, b);
	else 
	{
		modify(t[k].l, l, mid, a, mid);
		modify(t[k].r, mid + 1, r, mid + 1, b);
	}
	t[k].sum = t[ t[k].l ].sum + t[ t[k].r ].sum;
}

void insert()
{
	int k = 1, l = 1, r = n;
	while(l != r)
	{
		int mid = (l + r) >> 1;
		modify(root[k], 1, n, a, b);
		if(c <= mid) r = mid, k = k << 1;
		else l = mid + 1, k = k << 1|1;
	}
	modify(root[k], 1, n, a, b);
}

int solve()
{
	int k = 1, l = 1, r = n;
	while(l != r)
	{
		int mid = (l + r) >> 1;
		int t = query(root[k << 1], 1, n, a, b);
		if(t >= c) r = mid, k <<= 1;
		else l = mid + 1, k = k << 1|1, c -= t;
	}
	return l;
}