题意:
带修改的区间第K小.
SOL:
看了很久很久很久很久的整体二分,网上的各种题解也不是很多,也一直很不了解所谓的"贡献","将询问一起递归"是什么意思...看了一晚上的代码终于有所领悟...
什么是整体二分呢,"整体",整体整体什么是整体,整体就是将包括数,修改,询问一起二分,而如何实现呢?我看我能讲多少,那就算多少好了,还是代码更加直观.
先贴一下XHR大神犇的论文-----整体二分满足的性质(虽然没有完全理解但好像也很有道理的样子):
先讲一下判定答案是什么,我们对于一个询问时,我们可二分答案然后判断这个答案的rank,然后二分即可.在整体二分中,这个二分的值即为判定答案
1.询问的答案具有可二分性(显然啊...不然怎么叫做二分...)
2.修改对判定答案的贡献互相独立(比如说这个问题,添加一个比判定答案大,那么它就比判定答案大了,如果在添加一个比判定答案小的数,并不能对上一个修改构成什么影响...)
3.修改如果对判定答案有贡献,则贡献为以确定的与判定标准无关的值
4.贡献满足交换律,结合律,具有可加性.
(3,4的解释还是贴XHR大神的吧...我根本不能怎么表达...
因为贡献的值与判定标准无关,所以如果我们已经计算过某一些修改对询问的贡献,那么这个贡献永远不会改变------(若一个修改比判定答案大,那么它就比判定答案大了.你大爷永远是你大爷. ) 我们没有必要当判定标准改变时再次计算这部分修改的贡献,只要记录下当前的总贡献,在进一步二分时,直接加上新的贡献即可.
这部分还是讲不清楚啊...还是看代码比较直观...
5.题目允许离线算法(怎么感觉画风突变啊...一种忧桑的感觉)
对于这个题目应该怎么考虑呢...我们将所有的操作添加进一个序列中,然后对所有的询问用同一个二分答案作为判定答案,然后将所有应该增大判定答案的放在一组,减小的放在一组...啊啊啊啊真心说不明白,看代码看代码...加几个注释.
CODE:
/*==========================================================================
# Last modified: 2016-02-25 21:09
# Filename: 1901.cpp
# Description:
==========================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1]
#define maxn 100000
#define maxm 100000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline
void read(T& num) {
bool start=false,neg=false;
char c;
num=0;
while((c=getchar())!=EOF) {
if(c=='-') start=neg=true;
else if(c>='0' && c<='9') {
start=true;
num=num*10+c-'0';
} else if(start) break;
}
if(neg) num=-num;
}
/*==================split line==================*/
struct Infor{
int pos,x,id,op,k,l,r,cur;
//k,l,r,cur,id专门针对询问,分别表示询问第k大,l,r表示询问的范围,cur表示贡献---->放到程序中更好解释,表示询问的序号
//pos表示修改或原序列数值在序列中的位置
//op表示操作类型:1表示在序列中的元素,2表示修改前的元素-----这里又有一个奇技淫巧,我们将所有的信息--->原序列,修改,询问放在一个区间中,那么对于一个修改,到目前为止应该在序列中的元素则为修改后的元素,就在区间中新建一个位置放原来那个数,标记为2,修改后的数标记为1.
//x表示修改或原序列中的数值
}q[maxn],temp[maxn];
int c[maxn],a[maxn],ans[maxn],tmp[maxn];
bool mark[maxn];
int n,m,cnt=0,num=0;
//树状数组相关==================================================
void add(int x,int t){
while (x<=n){
c[x]+=t;
x+=lowbit(x);
}
}
int query(int x){
int ret=0;
while(x>0){
ret+=c[x];x-=lowbit(x);
}
return ret;
}
//==============================================================
void solve(int l,int r,int L,int R){//l,r表示正在进行二分的区间,L,R表示答案的范围
if (l>r) return;
if (L==R) { //如果答案已经确定了,那么这个区间内每一个询问的答案都是L
FORP(i,l,r) if (q[i].op==3) ans[q[i].id]=L;
return;
}
int mid=rs(L,R);
FORP(i,l,r){ //对于区间内每个的每个操作
if (q[i].op==1 && q[i].x<=mid) add(q[i].pos,1);
//如果这个元素应该在序列中存在,并且它会对当前的答案产生影响,我们将该位置加上1.
if (q[i].op==2 && q[i].x<=mid) add(q[i].pos,-1);
//奇技淫巧
//如果这个元素的op为2,那么之前一定有一个相等元素其op为1并且其已经对答案造成影响,如今这个元素被修改那么我们相应的要将它对答案的影响减去.
if (q[i].op==3) tmp[i]=query(q[i].r)-query(q[i].l-1);
//如果当前操作是询问操作,注意到一个时间性质,在这个询问之后的修改对这个询问没有影响,我们统计这个点询问范围内的贡献.
}
FORP(i,l,r){ //重置树状数组
if (q[i].op==1 && q[i].x<=mid) add(q[i].pos,-1);
if (q[i].op==2 && q[i].x<=mid) add(q[i].pos,1);
}
int tot=0;//统计在将区间二分时靠右操作的个数
FORP(i,l,r){//划分操作
if (q[i].op==3){ //这里就能体现cur的作用,如果当前比判断答案小的个数加上已经比判断答案小的个数大于k,那么我们要将判断答案减小,对于所有要这么操作的我们将它划到左边----于是就可以统一将判定答案的范围减小
if (q[i].cur+tmp[i]>=q[i].k) mark[i]=true,tot++;
else mark[i]=false, q[i].cur+=tmp[i];
}
else{
if (q[i].x<=mid) tot++,mark[i]=true; //对答案造成影响的,判定答案减小后仍可能造成影响.所以我们将它划到右边
else mark[i]=false;
}
}
int la=l,lb=l+tot;
FORP(i,l,r)
if (mark[i]) temp[la++]=q[i];
else temp[lb++]=q[i];
FORP(i,l,r) q[i]=temp[i]; //复制粘贴的过程
solve(l,la-1,L,mid);
solve(la,lb-1,mid+1,R); //整体二分的过程. 非常6
}
int main(){
//freopen("a.in","r",stdin);
//freopen("tmp.out","w",stdout);
read(n); read(m);
FORP(i,1,n){
read(a[i]);
q[++num].x=a[i]; q[num].pos=i; q[num].op=1; q[num].id=0;
} //读入原序列
FORP(i,1,m){
char s[5]; scanf("%s",s);
if (s[0]=='Q'){
int x,y,z; read(x); read(y); read(z);
q[++num].l=x; q[num].r=y; q[num].k=z;
q[num].id=++cnt; q[num].op=3;
}//读入询问
else {
int x,t;
read(t); read(x);
q[++num].x=a[t]; q[num].pos=t; q[num].id=0; q[num].op=2;//奇技淫巧,增加一个操作
q[++num].x=x; q[num].pos=t; q[num].id=0; q[num].op=1;
a[t]=x;
}//读入修改操作
}
solve(1,num,0,INF); //整体二分
FORP(i,1,cnt) printf("%d\n",ans[i]);//输出
}