HZOJ 数颜色
发布日期:2022-03-15 04:11:13 浏览次数:48 分类:技术文章

本文共 1511 字,大约阅读时间需要 5 分钟。

一眼看去树套树啊,我可能是数据结构学傻了……

是应该去学一下莫队进阶的东西了。

上面那个东西我没有打,所以这里没有代码,而且应该也不难理解吧。

这么多平衡树就算了,不过线段树还是挺好打的。

正解3:

主席树啊,其实并不需要再加一个树状数组,因为每次修改只影响两个,暴力修改就行了。

正解4:

分块(就是暴力但是跑的好快啊)。

下面是真正的正解:

将兔子以颜色为第一关键字,位置为第二关键字排序,通过二分就能找到一段区间内某种颜色兔子的数量。

至于修改,只需要找到两只兔子,将其位置互换即可,因为两只兔子是相邻的,所以并不会破坏有序性。

 

1 #include
2 #include
3 #include
4 #include
5 #include
6 #define LL long long 7 #define int LL 8 #define MAXN 300010 9 using namespace std;10 int n,m,b[MAXN];11 const int INF=0;12 pair
a[MAXN];13 inline int read();14 signed main()15 {16 // freopen("in.txt","r",stdin);17 18 n=read(),m=read();19 for(int i=1;i<=n;i++)a[i].first=read(),a[i].second=i,b[i]=a[i].first;//a[i]=read();20 sort(a+1,a+n+1);21 int op,x,l,r,c;22 for(int i=1;i<=m;i++)23 {24 op=read();25 if(op==1)26 {27 l=read(),r=read(),c=read();28 int len1=(upper_bound(a+1,a+n+1,make_pair(c,r))-a),len2=(lower_bound(a+1,a+n+1,make_pair(c,l))-a);29 printf("%lld\n",len1-len2);30 }31 else32 {33 x=read(); 34 if(b[x]==b[x+1])continue;35 int tem1=lower_bound(a+1,a+n+1,make_pair(b[x],x))-a,tem2=lower_bound(a+1,a+n+1,make_pair(b[x+1],x+1))-a;36 swap(a[tem1].second,a[tem2].second);swap(b[x],b[x+1]);37 }38 }39 }40 inline int read()41 {42 int s=0,f=1;char a=getchar();43 while(a<'0'||a>'9'){ if(a=='-')f=-1;a=getchar();}44 while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}45 return s*f;46 }
View Code

 

转载于:https://www.cnblogs.com/Al-Ca/p/11296094.html

转载地址:https://blog.csdn.net/weixin_30536513/article/details/99750234 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:黑盒测试-边界值
下一篇:如何快速分析一款ios软件或需求的大流程,然后在业务层实现,不牵扯到界面?...

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月05日 14时39分07秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql幻读是什么意思_MySQL中的幻读,你真的理解吗? 2019-04-21
mysql执行计划中性能最差的是_MySQL性能优化(七):MySQL执行计划,真的很重要,来一起学习吧... 2019-04-21
易语言执行mysql命令_易语言通过“打开”命令操作数据库 2019-04-21
mysql slave 1062_mysql主从同步slave错误1062 2019-04-21
mysql构造器_MySQL行构造器表达式优化(Row Constructor Expression) 2019-04-21
2008日志清理 server sql_SQL Server 2008 清除日志 2019-04-21
mac mysql root 权限_Mac平台重新设置MySQL的root密码 2019-04-21
mysql新增一列_MySQL-ProxySQL中间件 2019-04-21
mysql 30入门_30分钟带你快速入门MySQL教程 2019-04-21
kangle主机怎么配置MySQL_kangle web服务+easypanel主机控制面板快速搭建网站和数据库以及管理空间详细教程... 2019-04-21
mysql 翻页 存储过程_MySQl通用翻页(存储过程) 2019-04-21
2020word替换所有文本_Excel字符函数(5):REPLACE、SUBSTITUTE查找替换函数之区别... 2019-04-21
win10安装ipython_win10环境 ipython app.py 8080 这里为什么是ipython 这步无法启动 2019-04-21
假定在MYSQL_假定在名称为教学库的数据库中包含有学生、课程和选课三个表,它们的定义如下 - 问答库... 2019-04-21
mysql多字段存储过程_mysql 的存储过程_多字段 2019-04-21
python怎么创建字符串列表_如何在python列表中为每个字符串创建子列表? 2019-04-21
vba ado 执行多条mysql 语句_access 按钮 多条sql语句 VBA 2019-04-21
弹性方法计算连续梁板内力_(梁板结构)混凝土结构设计复习题及答案 2019-04-21
java root权限_android java获得root权限调用linux命令 | 学步园 2019-04-21
java最小化窗体_JAVA窗体最大化最小化控制+托盘 2019-04-21