Description
有 n 个位置和 m 个操作. 操作有两种, 每次操作如果是 1 a b c 的形式, 表示往第 a 个位置到第 b 个位置每个位置加入一个数 c. 如果操作形如 2 a b c 的形式, 表示询问从第 a 个位置到第 b 个位置, 第 c 大的数是多少.
Input
在输入文件 sequence.in 中, 第一行两个数 n,m. 意义如题目描述.
接下来 m 行每行形如 1 a b c 或者 2 a b c 如题目描述.
Output
在输出文件 sequence.out 中, 对于每个询问回答 k 大数是多少.
- 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
- Data Constraint
30% 的数据 n=m=1000
100% 的数据 n,m≤50000, 并且后 7 个点的数据 n,m 的范围从 32000 到 50000 近似成等差数列递增. a≤b≤n,1 操作中 | c|≤n,2 操作中 | c|≤maxlongint
Hint
第一个操作后位置 1 的数只有 1, 位置 2 的数也只有 1. 第二个操作后位置 1 的数有 1,2, 位置 2 的数也有 1,2. 第三次询问位置 1 到位置 1 第 2 大的数是 1. 第四次询问位置 1 到位置 1 第 1 大的数是 2. 第五次询问位置 1 到位置 2 第 3 大的数是 1.
题解
题目简洁大方, 好评!!!
这种题一般都是用树套树来做滴, 题目大意: 要求支持区间修改, 区间查询第 K 大
考虑一下 CDQ 分治, 先二分一个答案
我们就对于一下当前这一段的处理序列中, 先依次处理, 碰到询问就考虑是否可行
如果对于一个询问, 发现当前的 x 之下查询的 ans 大于那个值, 说明答案更小, 所以要放到左边去递归处理
但是同时记得, 把询问的值减掉查询出的 ans, 表示这一段肯定比它大, 先减掉
至于查询的话, 区间修改, 区间查询, 可以用树状数组就行了
代码
- #include <cstdio>
- #include <iostream>
- #include <cstring>
- #define ll long long
- #define N 50010
- using namespace std;
- int n,m,ans[N];
- ll sz1[N],sz2[N];
- bool bz[N];
- struct edge{ int d,x,y,c,op; }a[N],P[N],Q[N];
- void add(int x,int y) { for (int r=x;x<=n;x+=x&-x) sz1[x]+=y,sz2[x]+=r*y; }
- ll query(int x)
- {
- ll r=0;
- for (int i=x;i;i-=i&-i) r+=(x+1)*sz1[i]-sz2[i];
- return r;
- }
- void cdq(int L,int R,int l,int r)
- {
- if (L>R||l>r) return;
- if (l==r)
- {
- for (int i=L;i<=R;i++) ans[a[i].d]=l;
- return;
- }
- int mid=l+r+1>>1,num1=0,num2=0;ll x;
- for (int i=L;i<=R;i++)
- if (a[i].op==1)
- {
- if (a[i].c>=mid) add(a[i].x,1),add(a[i].y+1,-1),P[++num2]=a[i]; else Q[++num1]=a[i];
- }
- else
- {
- x=query(a[i].y)-query(a[i].x-1);
- if (x>=a[i].c) P[++num2]=a[i]; else a[i].c-=x,Q[++num1]=a[i];
- }
- for (int i=L;i<=R;i++) if (a[i].op==1&&a[i].c>=mid) add(a[i].x,-1),add(a[i].y+1,1);
- for (int i=1;i<=num1;i++) a[L+i-1]=Q[i];
- for (int i=1;i<=num2;i++) a[L+num1+i-1]=P[i];
- cdq(L,L+num1-1,l,mid-1),cdq(L+num1,R,mid,r);
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for (int i=1;i<=m;i++)
- {
- scanf("%d%d%d%d",&a[i].op,&a[i].x,&a[i].y,&a[i].c),a[i].d=i;
- if (a[i].op==2) bz[i]=1;
- }
- cdq(1,m,1,n);
- for (int i=1;i<=m;i++) if (bz[i]) printf("%d\n",ans[i]);
- }
[CDQ 分治][树状数组][树套树] Jzoj P3197 K 大数查询
来源: http://www.bubuko.com/infodetail-2938859.html