BZOJ2120数颜色(带修改莫队)
2024-08-29 03:02:35
莫队算法是一种数据结构的根号复杂度替代品,主要应用在询问[l,r]到询问[l+1,r]和[l,r+1]这两个插入和删除操作复杂度都较低的情况下。具体思想是:如果把一个询问[l,r]看做平面上的点(l,r)的话,两个询问状态之间的转移代价可以看做这两个点的曼哈顿距离。这样我们可以通过预处理出曼哈顿最小生成树解决这类问题,但莫队算法可以直接在根号复杂度下解决。
带修改莫队实际上是普通二维莫队的基础上增加了第三维(修改时间),这样就要求我们可以在较低复杂度下在某个区间内执行一个修改操作。以(l/B,r/B,t)为关键字,可以证明转移总复杂度为$O(n^{\frac{5}{3}})$的。
带修改莫队需要注意的地方:每个询问要记录这个询问之前的最后一个修改是哪个,每个修改要记录修改之前的值以方便撤销。修改函数要写两个,一个是执行某个修改操作,一个是没有修改地从某个[l,r]走到[l',r']。
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std; const int N=;
char s[];
struct P{ int l,r,id,t; }a[N];
struct Q{ int x,y,lst; }b[N];
int x,y,n,m,A,B,sum,l,r,t,cnt[N],v[N],ans[N],lst[N],bel[N]; bool cmp(const P &x,const P &y){
if (bel[x.l]!=bel[y.l]) return bel[x.l]<bel[y.l];
if (bel[x.r]!=bel[y.r]) return bel[x.r]<bel[y.r];
return x.t<y.t;
} void mdf(int x,int y){
if (x>=l && x<=r){
cnt[v[x]]--; if (!cnt[v[x]]) sum--;
v[x]=y;
cnt[y]++; if (cnt[y]==) sum++;
}else v[x]=y;
} void upd(int x,int y){
int p=cnt[v[x]]; cnt[v[x]]+=y;
if (!p && cnt[v[x]]) sum++;
if (p && !cnt[v[x]]) sum--;
} void work(){
l=,r=,t=;
rep(i,,A){
while (t>a[i].t) mdf(b[t].x,b[t].lst),t--;
while (t<a[i].t) t++,mdf(b[t].x,b[t].y);
while (r<a[i].r) r++,upd(r,);
while (l>a[i].l) l--,upd(l,);
while (r>a[i].r) upd(r,-),r--;
while (l<a[i].l) upd(l,-),l++;
ans[a[i].id]=sum;
}
} int main(){
freopen("bzoj2120.in","r",stdin);
freopen("bzoj2120.out","w",stdout);
scanf("%d%d",&n,&m); int B=sqrt(n);
rep(i,,n) scanf("%d",&v[i]),lst[i]=v[i],bel[i]=(i-)/B+;
rep(i,,m){
scanf("%s%d%d",s,&x,&y);
if (s[]=='Q') a[++A]=(P){x,y,A,B}; else b[++B]=(Q){x,y,lst[x]},lst[x]=y;
}
sort(a+,a+A+,cmp); work();
rep(i,,A) printf("%d\n",ans[i]);
return ;
}
最新文章
- 增强版字典DictionaryEx
- bash/shell编程学习(3)
- MySQL COLUMNS分区
- SharePoint 2013 BCS
- js-JavaScript高级程序设计学习笔记3
- Win7系统开放C盘下文件夹Everyone权限
- 有了malloc/free为什么还要new/delete ?
- CSS程序思想
- yii2 html下拉框
- VS2013 安装phonegap
- (原)Struts 相关资源下载
- php 异步处理的gearman
- php中mysql语句的基本写法
- c# 如何显示图片指定位置
- OC字符串的使用(一)
- Java中 == 和 equals()详解
- php通过ini_set调用output_compression压缩网页
- 【NFS】nfs安装调优
- vue 单页应用拆分为多页应用
- 【2018.08.19 C与C++基础】编程语言类型系统简介(草稿)
热门文章
- Linux内存初始化【转】
- error while loading shared libraries: libtest.so: cannot open shared object file: No such file or directory
- IOS使用命令行打包
- 移动端,PC端,微信等常用平台和浏览器判断
- Unix IPC之pipe
- sql查询与修改数据库逻辑文件名,移动数据库存储路径
- MIT6.006Lec03:插入排序,归并排序,递归树
- Spark(十二)SparkSQL简单使用
- 将C++ IplImage 图像用C#读取
- C#一步一步学网络辅助开发(1)--常用抓包工具的使用