洛谷 P1903 [国家集训队]数颜色
2024-10-02 06:44:07
题意简述
给定一个数列,支持两个操作
1.询问l~r有多少不同数字
2.修改某个数字
题解思路
带修莫队
如果修改多了,撤销修改
如果修改少了,进行修改
代码
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
struct Query
{
int l, r, t, i;
} qu[51000];
struct Modify
{
int p, col;
} mo[51000];
int n, m, cnt1, cnt2, len, s, l = 1, r, t;
int a[51000], c[1001000], ans[51000], tti[51000];
char opt;
bool cmp(const Query &x, const Query &y)
{
if (x.l / len != y.l / len) return x.l / len < y.l / len;
if (x.r / len != y.r / len) return x.r / len < y.r / len;
return x.t < y.t;
}
void add(int x) {s += !(c[x]++); }
void del(int x) {s -= !(--c[x]); }
void replace(int x)
{
int xx = mo[tti[t]].p;
if (xx >= l && xx <= r)
{
s -= !(--c[a[mo[tti[t]].p]]);
s += !(c[mo[tti[t]].col]++);
}
swap(a[mo[tti[t]].p], mo[tti[t]].col);
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (register int i = 1; i <= n; ++i) cin >> a[i];
for (register int i = 1; i <= m; ++i)
{
cin >> opt;
if (opt == 'Q')
{
++cnt1;
cin >> qu[cnt1].l >> qu[cnt1].r;
qu[cnt1].t = i;
qu[cnt1].i = cnt1;
}
else
{
++cnt2;
cin >> mo[cnt2].p >> mo[cnt2].col;
tti[i] = cnt2;
}
}
len = n * pow(cnt2, 1.0 / 3);
len = pow(n, 2.0 / 3);
sort(qu + 1, qu + cnt1 + 1, cmp);
for (register int i = 1; i <= cnt1; ++i)
{
while (l > qu[i].l) add(a[--l]);
while (r < qu[i].r) add(a[++r]);
while (l < qu[i].l) del(a[l++]);
while (r > qu[i].r) del(a[r--]);
while (t < qu[i].t) if (tti[++t]) replace(t);
while (t > qu[i].t) if (tti[--t]) replace(t);
ans[qu[i].i] = s;
}
for (register int i = 1; i <= cnt1; ++i) cout << ans[i] << endl;
}
最新文章
- python学习笔记(字符串操作、字典操作、三级菜单实例)
- mysql my.cnf 配置详解
- Redis &; Python/Django 简单用户登陆
- SharePoint服务器端对象模型 之 访问用户、用户组和权限(Part 1)
- 【crunch bang】 增加“菜单项”
- Xcode运行的错误bug收集
- VisualSVN Server的windows 2003配置和使用方法(图文并茂)
- Spark Streaming揭秘 Day22 架构源码图解
- HDU 畅通工程系列
- Spring MVC视图层:thymeleaf vs. JSP
- 如何创建一个要素数据类 IField,IFieldEdit,IFields,IFieldsEditI,GeometryDef,IGeometryDefEdit接口
- vue cli创建的项目 当你后期使用了ES6语法,如何解决浏览器兼容问题
- 2018-2019-2 20165225《网络对抗技术》Exp1 缓冲区溢出实验
- thinkphp 把小程序码二进制流存储到本地
- 如何用ABP框架快速完成项目(14) - 结尾? 当然不是, 这只是开始!
- 乘风破浪:LeetCode真题_034_Find First and Last Position of Element in Sorted Array
- Centos6.4下安装protobuf-c问题及解决办法
- bzoj1103【POI2007】大都市meg
- sklearn 中的 Pipeline 机制 和FeatureUnion
- 使用axios发送post请求,将JSON数据改为为form类型
热门文章
- WebApi 通过拦截器设置特定的返回格式
- Socket编程:listen()函数英文翻译
- WEB前端--返回顶部特效源码
- STM32F072从零配置工程-自定义时钟配置详解
- CF1194D 1-2-K Game (博弈论)
- 生成数据库自增不重复ID的方法
- 如果通过脚本来关闭程序-linux
- https://www.cnblogs.com/M-LittleBird/p/5902850.html
- Java面试题 从源码角度分析HashSet实现原理?
- ==和equals的区别,85%的求职者“理直气壮”地回答错误