BZOJ 2120 带修莫队
2024-08-24 07:44:47
思路:
暴力能过的 嘿嘿嘿
我是来练带修莫队的嗯 复杂度 O(n^5/3)
//By SiriusRen
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1050000;
int n,m,a[N],cnt1,cnt2,Block,block[N],xx,yy,ans,sum[N],last[N],Ans[N];
char op[105];
struct Query{
int L,R,time,id;
Query(int LL,int RR,int TT,int II){
L=LL,R=RR,time=TT,id=II;
}Query(){}
}query[N];
struct Change{
int position,color,lastcolor;
Change(int II,int CC,int LL){
position=II,color=CC,lastcolor=LL;
}Change(){}
}change[N];
bool operator<(Query a,Query b){
if(block[a.L]==block[b.L]){
if(a.R!=b.R)return a.R<b.R;
return a.time<b.time;
}
return block[a.L]<block[b.L];
}
void update(int x,int f){
if(f==1){if(!sum[x])ans++;sum[x]++;}
else if(f==-1){if(sum[x]==1)ans--;sum[x]--;}
}
int main(){
scanf("%d%d",&n,&m);
Block=(int)pow(n,2.0/3.0);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),last[i]=a[i],block[i]=(i-1)/Block+1;
for(int i=1;i<=m;i++){
scanf("%s%d%d",op,&xx,&yy);
if(op[0]=='Q')query[++cnt1]=Query(xx,yy,cnt2,cnt1);
else change[++cnt2]=Change(xx,yy,last[xx]),last[xx]=yy;
}
sort(query+1,query+1+cnt1);
for(int L=1,R=0,i=1,T=0;i<=cnt1;i++){
for(;T<query[i].time;T++){
if(change[T+1].position>=L&&change[T+1].position<=R)
update(a[change[T+1].position],-1),update(change[T+1].color,1);
a[change[T+1].position]=change[T+1].color;
}
for(;T>query[i].time;T--){
if(change[T].position>=L&&change[T].position<=R)
update(a[change[T].position],-1),update(change[T].lastcolor,1);
a[change[T].position]=change[T].lastcolor;
}
for(;R<query[i].R;R++)update(a[R+1],1);
for(;R>query[i].R;R--)update(a[R],-1);
for(;L<query[i].L;L++)update(a[L],-1);
for(;L>query[i].L;L--)update(a[L-1],1);
Ans[query[i].id]=ans;
}
for(int i=1;i<=cnt1;i++)printf("%d\n",Ans[i]);
}
最新文章
- 子级与父级的margin合并的问题
- 点击每个li节点,都弹出其文本值及修改
- javase基础复习攻略《七》
- HttpURLConnection请求接口
- Java拾穗
- 港交所OMD-C对接笔记
- python学习笔记(四)-数据类型
- C#面试常见题目
- (生活)Photoshop入门(不定时更新)
- 生成命令行接口--google开源的fire使用体验【python-fire】
- React基础篇 - 02.JSX 简介
- EF-CodeFirst-域模型配置
- hessian 在spring中的使用 (bean 如 Dao无法注入的问题)
- eclipse整合spring+springMVC+Mybatis
- Scrum Meeting 10.28
- 架构师养成记--37.简单shell编程
- 十二步创建你的第一个JavaScript库
- SQL Server 自动备份数据脚本
- 多个else if语句
- BZOJ 2457 双端队列
热门文章
- hdu1811 Rank of Tetris 拓扑排序+并查集
- 【Oracle】DBMS_STATS.GATHER_TABLE_STATS分析表
- ES: 机器学习、专家系统、控制系统的数学映射
- openlayers5学习笔记-001
- eclipse tomcat发布路径在哪?
- 2104 -- K-th Number
- BZOJ 2716/2648 SJY摆棋子 (三维偏序CDQ+树状数组)
- BA-防冻开关的安装
- C++ 浅析 STL 中的 list 容器
- node-webkit 屏幕截图功能