【分块】bzoj2453 维护队列
2024-09-04 14:42:29
http://www.cnblogs.com/autsky-jadek/p/4020296.html
同bzoj2120。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,sz,sum,l[],r[],num[],pre[],preb[],a[],x,y,pos[];
int Res,Num;char C,CH[];
inline int G()
{
Res=;C='*';
while(C<''||C>'')C=getchar();
while(C>=''&&C<=''){Res=Res*+(C-'');C=getchar();}
return Res;
}
inline void P(int x)
{
Num=;if(!x){putchar('');puts("");return;}
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);
puts("");
}
void makeblock()
{
sz=sqrt((double)n*log2(n)); if(!sz) sz=;
for(sum=;sum*sz<n;sum++)
{
l[sum]=(sum-)*sz+;
r[sum]=sum*sz;
for(int i=l[sum];i<=r[sum];i++)
num[i]=sum;
}
l[sum]=sz*(sum-)+;
r[sum]=n;
for(int i=l[sum];i<=r[sum];i++)
num[i]=sum;
}
void makepre()
{
for(int i=;i<=n;i++) {pre[i]=pos[a[i]]; pos[a[i]]=i;}
memcpy(preb,pre,sizeof(pre));
for(int i=;i<=sum;i++) sort(pre+l[i],pre+r[i]+);
}
inline void query()
{
int res=;
if(num[x]+>=num[y]) {for(int i=x;i<=y;i++) if(preb[i]<x) res++;}
else
{
for(int i=x;i<=r[num[x]];i++) if(preb[i]<x) res++;
for(int i=l[num[y]];i<=y;i++) if(preb[i]<x) res++;
for(int i=num[x]+;i<num[y];i++) res+=lower_bound(pre+l[i],pre+r[i]+,x)-(pre+l[i]);
}
P(res);
}
inline void update()
{
int t=;
for(int i=x+;i<=n;i++)
if(a[i]==y)
{*lower_bound(pre+l[num[i]],pre+r[num[i]],preb[i])=x; preb[i]=x;
sort(pre+l[num[i]],pre+r[num[i]]+); break;}
a[]=y;
for(int i=x-;i>=;i--)
if(a[i]==y)
{*lower_bound(pre+l[num[x]],pre+r[num[x]],preb[x])=i; preb[x]=i;
sort(pre+l[num[x]],pre+r[num[x]]+); break;}
int t2=a[x]; a[x]=y;
for(int i=x;i>=;i--)
if(a[i]==t2)
{t=i; break;}
for(int i=x+;i<=n;i++)
if(a[i]==t2)
{*lower_bound(pre+l[num[i]],pre+r[num[i]],preb[i])=t; preb[i]=t;
sort(pre+l[num[i]],pre+r[num[i]]+); break;}
}char op[];
int main()
{
n=G();m=G();
for(int i=;i<=n;i++) a[i]=G();
makeblock(); makepre();
for(int i=;i<=m;i++)
{
scanf("%s",op);x=G();y=G();
if(op[]=='Q') query();
else update();
}
return ;
}
最新文章
- 2 . Linux常见命令
- linux基础-第八单元 正文处理命令及tar命令
- 3到6年的.NETer应该掌握哪些知识?
- 3_STL算法
- PHP 二维码解码 (读取二维码)
- outlook新邮件到达提醒设置以及outlook最小化到托盘设置
- Leetcode006 ZigZag Conversion
- Java基本排序
- Spark常见错误汇总
- 由于权限不足而无法读取配置文件出现的HTTP 500.19解决办法
- linux 学习之九、Linux 磁盘与文件系统管理(2)
- IOS开发:xcode5版本引发的问题
- 如何制作一个类似Tiny Wings的游戏 Cocos2d-x 2.1.4
- android--listview设置高度
- C++通用WMI接口实现获取Windows操作系统内核版本号
- 【一本通1248:Dungeon Master&;&;洛谷UVA532 Dungeon Master】
- sql中的等于和不等于, &#39;=&#39; ,&#39;!=&#39;,&#39;<;>;&#39;,&#39;is null&#39;....
- centos7下安装docker(21docker swarm集群创建)
- Linux基础(五) Shell函数
- maven项目强制自动更新所有jar包
热门文章
- python 一些乱七八糟的东西
- CentOS 6.4安装配置ldap
- 编译 openssl 0.9.8zc 出现 error C2220: warning treated as error - no &#39;object&#39; file generated
- Nginx配置配置文件详解
- idea控制台中文乱码问题解决办法
- idea 从远程仓库导入git项目
- bzoj1503 郁闷的出纳员 splay版
- [转载]解决clickonce不支持administer权限问题
- LeetCode 6:Excel Sheet Column Number
- Windows 的GUID