注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

bzoj1901【ZJU2112】Dynamic Rankings解题报告  

2014-04-18 12:10:00|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目链接

带单点修改的区间k大,直接树状数组套主席树。

主席树介绍传送门

放上代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define maxnode 4000010
#define maxn 10010
#define maxm 10010

inline void read(int &x)
{
x=0;
bool flag=false;
char ch=getchar();
while (ch<'0' || ch>'9')
{
if (ch=='-') flag=true;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
if (flag) x=-x;
}
inline void read(char &c)
{
c=getchar();
while (c==' ' || c=='\n' || c=='\r') c=getchar();
}
inline int lowbit(int x)
{
return x&(-x);
}

struct segment_tree
{
int left,right;
int num;
} node[maxnode];
struct Ask
{
bool flag;
int x,y,z;
} ask[maxm];
int n,m,tot,q,q2;
int num[20010],num2[20010];
int c[maxn];
int a[maxn];

int find(int x)
{
int l=1,r=q2;
while (l<=r)
{
int mid=(l+r)>>1;
if (num2[mid]==x) return mid;
if (num2[mid]<x) l=mid+1;
else r=mid-1;
}
}
inline int newnode()
{
tot++;
node[tot]=(segment_tree){0,0,0};
return tot;
}

void tree_insert(int x,int y,int z)
{
if (c[x]==0) c[x]=newnode();
x=c[x];
int l=1,r=q2;
while (true)
{
node[x].num+=z;
if (l==r) return;
int mid=(l+r)>>1;
if (y<=mid)
{
if (node[x].left==0) node[x].left=newnode();
x=node[x].left;
r=mid;
} else
{
if (node[x].right==0) node[x].right=newnode();
x=node[x].right;
l=mid+1;
}
}
}
void insert(int x,int y,int z)
{
for (int j=x;j<=n;j+=lowbit(j))
tree_insert(j,y,z);
}
void work(int x,int y,int z)
{
int Q[1010],size1=0;
int Q2[1010],size2=0;
for (int i=y;i>0;i-=lowbit(i))
if (c[i]) Q[++size1]=c[i];
for (int j=x-1;j>0;j-=lowbit(j))
if (c[j]) Q2[++size2]=c[j];
int l=1,r=q2;
while (z>0)
{
if (l==r) break;
int mid=(l+r)>>1;
int tmp=0;
for (int it=0;it<=size1;it++)
tmp+=node[node[Q[it]].left].num;
for (int it=0;it<=size2;it++)
tmp-=node[node[Q2[it]].left].num;
if (z<=tmp)
{
r=mid;
int size=size1;
size1=0;
for (int i=1;i<=size;i++)
{
int tmp2=Q[i];
if (node[tmp2].left) Q[++size1]=node[tmp2].left;
}
size=size2;
size2=0;
for (int i=1;i<=size;i++)
{
int tmp2=Q2[i];
if (node[tmp2].left) Q2[++size2]=node[tmp2].left;
}
} else
{
z-=tmp;
l=mid+1;
int size=size1;
size1=0;
for (int i=1;i<=size;i++)
{
int tmp2=Q[i];
if (node[tmp2].right) Q[++size1]=node[tmp2].right;
}
size=size2;
size2=0;
for (int i=1;i<=size;i++)
{
int tmp2=Q2[i];
if (node[tmp2].right) Q2[++size2]=node[tmp2].right;
}
}
}
printf("%d\n",num2[l]);
}

int main()
{
read(n),read(m);
for (int i=1;i<=n;i++)
{
read(a[i]);
num[q++]=a[i];
}
for (int i=0;i<m;i++)
{
char ch;
int x,y,z;
read(ch);
if (ch=='C')
{
read(x),read(y);
num[q++]=y;
ask[i]=(Ask){0,x,y,0};
}
if (ch=='Q')
{
read(x),read(y),read(z);
ask[i]=(Ask){1,x,y,z};
}
}
sort(num,num+q);
num2[1]=num[0];q2=1;
for (int i=1;i<q;i++)
if (num[i]!=num[i-1]) num2[++q2]=num[i];
for (int i=1;i<=n;i++)
insert(i,find(a[i]),1);
for (int i=0;i<m;i++)
if (!ask[i].flag)
{
insert(ask[i].x,find(a[ask[i].x]),-1);
insert(ask[i].x,find(ask[i].y),1);
a[ask[i].x]=ask[i].y;
} else
work(ask[i].x,ask[i].y,ask[i].z);
return 0;
}


  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018