[UVa12345] Dynamic len (带 修 )
2024-08-26 16:40:23
题意:有n个数编号从0→n-1,两种操作:
Q L R:询问编号为L→R-1的数中共有多少种不同的数
M X Y:将编号为X的数改为Y
共有m个操作
题目 链接 : https://vjudge.net/problem/UVA-12345
#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define dep(i,j,k) for(int i=k;i>=j;i--)
#define INF 0x3f3f3f3f
#define mem(i,j) memset(i,0,sizeof(i))
#define make(i,j) make_pair(i,j)
using namespace std;
const int N=1e6+;
int a[N],pos[N],num[N],now[N],ans[N],l=,r=,tmp;
struct noq {
int l,r,id,t;
}q[N];
struct noc {
int x,old,ne;
}c[N];
bool cmp(noq a,noq b) {
if(pos[a.l]==pos[b.l]) {
if(pos[a.r]==pos[b.r]) return a.t<b.t;
return pos[a.r]<pos[b.r];
}
return pos[a.l]<pos[b.l];
}
void add(int x,int d) {
num[x]+=d;
if(d> && num[x]==) tmp++;
else if(d< && num[x]==) tmp--;
}
void go(int x,int ne) {
if(l<=x && x<=r) {
add(a[x],-); add(ne,);
}
a[x]=ne;
}
int main() {
int n,m; int head=,tail=;
scanf("%d %d",&n,&m); int M=(int)pow(n,0.666666);
rep(i,,n) {
scanf("%d",&a[i]);
now[i]=a[i];
pos[i]=(i-)/M;
}
rep(i,,m) {
char ch[]; int x,y;
scanf("%s",ch);
scanf("%d %d",&x,&y); x++;
if(ch[]=='Q') q[++head]=(noq){x,y,head,tail};
else {
c[++tail]=(noc){x,now[x],y};
now[x]=y;
}
}
sort(q+,q++head,cmp); int t=;
rep(i,,head) {
while(t<q[i].t) go(c[t+].x,c[t+].ne),++t;
while(t>q[i].t) go(c[t].x,c[t].old),--t;
while(l<q[i].l) add(a[l++],-);
while(l>q[i].l) add(a[--l],);
while(r<q[i].r) add(a[++r],);
while(r>q[i].r) add(a[r--],-);
ans[q[i].id]=tmp;
}
rep(i,,head) printf("%d\n",ans[i]);
return ;
}
最新文章
- nginx在linux下安装
- Google Chrome开发者工具
- IPC_共享内存
- cocos2dx json数据解析
- Maven解决Missing artifact com.sun:tools:jar:1.5.0错误
- [转] React Native Navigator — Navigating Like A Pro in React Native
- [android开发之内容更新类APP]二、这几日的结果
- mysql学习(八)数据表类型-字符集
- Error pulling origin: error: Your local changes to the following files would be overwritten by merge
- Django中请求的生命周期
- selenium自动化测试——常见的八种元素定位方法
- 【MM系列】SAP MB1A MB1B MB1C MB11 MIGO的区别解析
- commons-lang3-3.2.jar中的常用工具类的使用
- find_first_zero_bit在使用gcc 4.2.4 编译时,需要保护%eax
- vue axios请求/响应拦截器
- kvm 创建新虚拟机命virt-install 使用说明
- sqlserver将数据库的数据导成excel文档方法
- Ubuntu apt-get方式安装Subversion
- JQuery学习---JQuery深入学习
- 移动端车牌识别/车牌OCR识别