方法一，树套树
外层权值线段树记值域,内层平衡树记权值
修改就删掉原来的再加上新的
查询区间kth,就先二分值域,对于每个值域,查询一下下标在[l,r]区间内的数有多少个,然后跳就可以了
时间复杂度 (O(mlog^2 n)) 空间复杂度 (O(nlogn))
lg数据太毒瘤
...
拼命优化 本机3.3s,交上去一样T
可能treap会快一些?但是估计快不了1.3s,
qwq
Code:
/*
@Date : 2019-07-08 18:33:36
@Author : Adscn (adscn@qq.com)
@Link : https://www.cnblogs.com/LLCSBlog
*/
#define FASTER
#ifdef FASTER
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#endif
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi io.xint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(ch<'0'|ch>'9')ch=='-'?f=1:f,ch=gc;
while(ch>='0'&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
IL unsigned int LOG2(unsigned int x)
{
unsigned int ret;
__asm__ __volatile__ ("bsrl %1, %%eax":"=a"(ret):"m"(x));
return ret;
}
struct FastIO {
static const int S = 1e7;
int wpos;
char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar() {
static char buf[S];
static int len = 0, pos = 0;
if (pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if (pos == len) exit(0);
return buf[pos++];
}
inline int xuint() {
int c = xchar(), x = 0;
while (c <= 32) c = xchar();
for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
inline int xint()
{
int s = 1, c = xchar(), x = 0;
while (c <= 32) c = xchar();
if (c == '-') s = -1, c = xchar();
for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x * s;
}
inline void xstring(char *s)
{
int c = xchar();
while (c <= 32) c = xchar();
for (; c > 32; c = xchar()) * s++ = c;
*s = 0;
}
inline void wchar(int x)
{
if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos++] = x;
}
inline void wint(int x)
{
if (x < 0) wchar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n) s[n++] = '0' + x % 10, x /= 10;
while (n--) wchar(s[n]);
wchar('
');
}
inline void wstring(const char *s)
{
while (*s) wchar(*s++);
}
~FastIO()
{
if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;
const int MAXN=1e5+7;
const int __SIZE_OF_MEM=4e6;
struct SplayTree{
struct node;
typedef node* tree;
struct node{
tree ch[2],par;
int val,siz,cnt;
node(){}
node(int v,tree p){val=v,par=p;siz=cnt=1;ch[0]=ch[1]=NULL;}
}*root;
static node mem[__SIZE_OF_MEM],*stk[__SIZE_OF_MEM],**top;
inline tree newnode(int v,tree p)
{
tree k=*--top;
k->siz=k->cnt=1,k->ch[0]=k->ch[1]=NULL;
k->val=v,k->par=p;
return k;
}
inline void delnode(tree &x){*top++=x;x=0;}
SplayTree(){clear();}
inline int siz(tree x){return x?x->siz:0;}
inline int ws(tree x,tree p){return p?p->ch[1]==x:0;}
inline void connect(tree x,tree p,int wh){if(x)x->par=p;(p?p->ch[wh]:root)=x;}
inline void pushup(tree x){if(x)x->siz=siz(x->ch[0])+siz(x->ch[1])+x->cnt;}
inline void rotate(tree x)
{
tree p=x->par,g=p->par;
bool t=ws(x,p);
connect(x,g,ws(p,g));
connect(x->ch[!t],p,t);
connect(p,x,!t);
pushup(p);
}
inline void Splay(tree x,tree y)
{
if(!x)return;
while(x->par!=y)
{
tree p=x->par,g=p->par;
if(g!=y)rotate(ws(x,p)^ws(p,g)?x:p);
rotate(x);
}
pushup(x);
}
public:
inline void insert(int val)
{
if(!root){root=newnode(val,NULL);return;}
#define nxt (val>=x->val)
for(tree x=root;x;x=x->ch[nxt])
{
if(x->val==val)
{
++x->cnt;
Splay(x,NULL);
return;
}
if(!x->ch[nxt])
{
x->ch[nxt]=newnode(val,x);
Splay(x->ch[nxt],NULL);
return;
}
}
#undef nxt
}
inline void find(int val)
{
tree x=root;
while(x&&x->ch[val>x->val]&&x->val!=val)x=x->ch[val>x->val];
Splay(x,NULL);
}
inline int rank(int val)
{
insert(val);
int ans=siz(root->ch[0])+root->cnt-1;
del(val);
return ans;
}
inline void del(int val)
{
if(empty())return;
find(val);
tree x=root;
if(x->val!=val)return;
if(x->cnt>1){--x->cnt,--x->siz;return;}
if(!x->ch[0])
{
root=x->ch[1];
if(root)root->par=NULL;
delnode(x);
return;
}
tree k=x->ch[0];
while(k->ch[1])k=k->ch[1];
Splay(k,x);
root=k,k->par=NULL;
connect(x->ch[1],k,1);
pushup(k);
delnode(x);
}
inline int num(int l,int r){/*cout<<l<<" "<<r<<endl;*/return rank(r)-rank(l-1);}
inline void clear(){root=NULL;}
inline bool empty(){return root==NULL;}
inline void print(){_print(root);puts("");}
private:
inline void _print(tree x)
{
if(!x)return;
_print(x->ch[0]);
printf("%d ",x->val);
_print(x->ch[1]);
}
};
SplayTree::node
SplayTree::mem[__SIZE_OF_MEM],
*SplayTree::stk[__SIZE_OF_MEM],
**SplayTree::top=SplayTree::stk+__SIZE_OF_MEM;
const int MX=4e6;
struct node;
typedef node* tree;
struct node{
SplayTree t;
tree l,r;
inline void insert(int k){t.insert(k);}
inline void del(int k){t.del(k);}
inline bool empty(){return t.empty();}
inline int num(int l,int r){/*cout<<(int)t->root;*/return t.num(l,r);}
}*root,mem[MX],*stk[MX],**top=stk+MX;
inline tree newnode()
{
tree p=*--top;
p->l=p->r=0;
p->t.clear();
return p;
}
inline void insert(tree &rt,int x,int y,int L=0,int R=1e9)
{
if(!rt)rt=newnode();
rt->insert(y);
if(L==R)return;
int mid((L+R)>>1);
if(x<=mid)insert(rt->l,x,y,L,mid);
else insert(rt->r,x,y,mid+1,R);
}
inline void del(tree &rt,int x,int y,int L=0,int R=1e9)
{
rt->del(y);
if(L==R)return;
int mid((L+R)>>1);
if(x<=mid)del(rt->l,x,y,L,mid);
else del(rt->r,x,y,mid+1,R);
}
inline int num(tree &rt,int k,int l_,int r_,int L=0,int R=1e9)
{
if(L==R)return L;
int lsiz=rt->l?rt->l->num(l_,r_):0;
int mid((L+R)>>1);
if(lsiz>=k)return num(rt->l,k,l_,r_,L,mid);
return num(rt->r,k-lsiz,l_,r_,mid+1,R);
}
int a[MAXN];
signed main(void)
{
// File("lg2617");
// clock_t start,finish;
// start=clock();
for(SplayTree::node **bg=SplayTree::stk,*cp=SplayTree::mem,**ed=bg+__SIZE_OF_MEM;bg!=ed;)*(bg++)=cp++;
for(node **bg=stk,*cp=mem,**ed=bg+MX;bg!=ed;)*(bg++)=cp++;
int n=gi,m=gi;
for(int i=1;i<=n;++i)a[i]=gi;
for(int i=1;i<=n;++i)insert(root,a[i],i);
while(m--)
{
char type=io.xchar();
while(type!='Q'&&type!='C')type=io.xchar();
int l,r,k;
if(type=='Q')
{
l=gi,r=gi,k=gi;
io.wint(num(root,k,l,r));
}
if(type=='C')
{
l=gi,k=gi;
del(root,a[l],l);
insert(root,a[l]=k,l);
}
}
// finish=clock();
// cerr<<(double)(finish-start)/CLOCKS_PER_SEC<<"s";
return 0;
}
方法二
树状数组套动态开点值域线段树(主席树)
时间复杂度(O(mlog^{2}n))
空间复杂度(O(nlog^{2}n))
大概可以这么理解,树状数组跳lowbit的时候,一定可以保证你想访问的一个前缀被不重不漏地遍历到。
另外，我们发现，主席树做静态区间kth的时候，如果要更新，要更新n个线段树，时间复杂度无法接受。
但查询很快。
对于这种数据结构题，我们有个通用的套路，就是尽量让询问和修改的复杂度相等，这样整体的复杂度越低。
于是我们考虑树状数组下套一个线段树,代码也很简洁，如下
for(int i=pos;i<=n;i+=i&-i)modify(rt[i],val,v,1,tot);
这样想，假如线段树每次都全部修改，全部查询，那么和原来的c数组是等价的
那么我们现在换成高级的数据结构，每次查询前k个，那么我们还是能保证不重不漏的更新与查询。
就是这样
要离散化一下，因为有修改，所以就预先读入完，然后离散化后离线回答
如果强制在线，应该可以用平衡树来维护
Code:
/*
@Date : 2019-07-08 18:33:36
@Author : Adscn (adscn@qq.com)
@Link : https://www.cnblogs.com/LLCSBlog
*/
//#define FASTER
#ifdef FASTER
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#endif
#include<bits/stdc++.h>
#include<unistd.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(ch<'0'|ch>'9')ch=='-'?f=1:f,ch=gc;
while(ch>='0'&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
if(k<0)k=-k,putchar('-');
if(k>=10)pi(k/10,0);
putchar(k%10+'0');
if(ch)putchar(ch);
}
IL unsigned int LOG2(unsigned int x)
{
unsigned int ret;
__asm__ __volatile__ ("bsrl %1, %%eax":"=a"(ret):"m"(x));
return ret;
}
const int MAXN=1e5+7;
struct node{
int v,l,r;
}t[MAXN*500];
int n,m;
int rt[MAXN],cnt;
int qx[MAXN],qy[MAXN],cntx,cnty;
struct oper{
int type;
int l,r,k;
int pos,val;
}q[MAXN];
int tot;
int a[MAXN],b[MAXN*2];
void modify(int &now,int pos,int val,int l,int r)
{
if(!now)now=++cnt;
t[now].v+=val;
if(l>=r)return;
int mid=(l+r)>>1;
//cerr<<l<<" "<<mid<<" "<<r<<endl;
if(pos<=mid)modify(t[now].l,pos,val,l,mid);
else modify(t[now].r,pos,val,mid+1,r);
}
inline void add(int pos,int v)
{
int val=lower_bound(b+1,b+tot+1,a[pos])-b;
for(int i=pos;i<=n;i+=i&-i)modify(rt[i],val,v,1,tot);
}
inline int query(int l,int r,int k,int sum=0)
{
if(l==r)return l;
int mid=(l+r)>>1;
for(int i=1;i<=cntx;++i)sum-=t[t[qx[i]].l].v;
for(int i=1;i<=cnty;++i)sum+=t[t[qy[i]].l].v;
if(k<=sum)
{
for(int i=1;i<=cntx;++i)qx[i]=t[qx[i]].l;
for(int i=1;i<=cnty;++i)qy[i]=t[qy[i]].l;
return query(l,mid,k);
}
else
{
for(int i=1;i<=cntx;++i)qx[i]=t[qx[i]].r;
for(int i=1;i<=cnty;++i)qy[i]=t[qy[i]].r;
return query(mid+1,r,k-sum);
}
}
int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
File("file");
#endif
n=gi,m=gi;
for(int i=1;i<=n;++i)a[i]=gi,b[++tot]=a[i];
for(int i=1;i<=m;++i)
{
char ch=getchar();
while(ch!='Q'&&ch!='C')ch=getchar();
if(ch=='Q')
{
q[i].type=1;
q[i].l=gi,q[i].r=gi,q[i].k=gi;
}
if(ch=='C')
{
q[i].type=0;
q[i].pos=gi,q[i].val=gi;
b[++tot]=q[i].val;
}
}
sort(b+1,b+tot+1);
tot=unique(b+1,b+tot+1)-b-1;
for(int i=1;i<=n;++i)add(i,1);
for(int i=1;i<=m;++i)
{
if(q[i].type)
{
cntx=cnty=0;
for(int j=q[i].r;j;j-=j&-j)qy[++cnty]=rt[j];
for(int j=q[i].l-1;j;j-=j&-j)qx[++cntx]=rt[j];
pi(b[query(1,tot,q[i].k)],'
');
}
else add(q[i].pos,-1),a[q[i].pos]=q[i].val,add(q[i].pos,1);
}
return 0;
}