[luogu]P3939 数颜色[二分]
数颜色
题目描述
小 C 的兔子不是雪白的,而是五彩缤纷的。每只兔子都有一种颜色,不同的兔子可能有 相同的颜色。小 C 把她标号从 1 到 n 的 n 只兔子排成长长的一排,来给他们喂胡萝卜吃。 排列完成后,第 i 只兔子的颜色是 ai。
俗话说得好,“萝卜青菜,各有所爱”。小 C 发现,不同颜色的兔子可能有对胡萝卜的 不同偏好。比如,银色的兔子最喜欢吃金色的胡萝卜,金色的兔子更喜欢吃胡萝卜叶子,而 绿色的兔子却喜欢吃酸一点的胡萝卜……为了满足兔子们的要求,小 C 十分苦恼。所以,为 了使得胡萝卜喂得更加准确,小 C 想知道在区间 [lj,rj] 里有多少只颜色为 cj 的兔子。
不过,因为小 C 的兔子们都十分地活跃,它们不是很愿意待在一个固定的位置;与此同 时,小 C 也在根据她知道的信息来给兔子们调整位置。所以,有时编号为 xj 和 xj+1 的两 只兔子会交换位置。 小 C 被这一系列麻烦事给难住了。你能帮帮她吗?
输入输出格式
输入格式:
从标准输入中读入数据。 输入第 1 行两个正整数 n,m。
输入第 2 行 n 个正整数,第 i 个数表示第 i 只兔子的颜色 ai。
输入接下来 m 行,每行为以下两种中的一种:
“1 lj rj cj”
:询问在区间 [lj,rj] 里有多少只颜色为 cj 的兔子;
“2 xj”:xj 和 xj+1 两只兔子交换了位置。
输出格式:
输出到标准输出中。
对于每个 1 操作,输出一行一个正整数,表示你对于这个询问的答案。
输入输出样例
输入样例1#:
6 5
1 2 3 2 3 3
1 1 3 2
1 4 6 3
2 3
1 1 3 2
1 4 6 3
输出样例1#:
1
2
2
3
说明
【样例 1 说明】
前两个 1 操作和后两个 1 操作对应相同;在第三次的 2 操作后,3 号兔子和 4 号兔子
交换了位置,序列变为 1 2 2 3 3 3。
【数据范围与约定】
子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难,可以尝试只解 决一部分测试数据。 对于所有测试点,有 1≤lj<rj≤n,1≤xj<n。 每个测试点的数据规模及特点如下表:
图来自luogu:
特殊性质 1:保证对于所有操作 1,有∣rj−lj∣≤20 或∣rj−lj∣≤n−20。
特殊性质 2:保证不会有两只相同颜色的兔子。
一开始想到一个离线的方法,并且交换只换相邻两个,所以我只需考虑边界的情况,后面发现不对啊,里面的元素可以跑到外面啊,气死我了。
...
正解说是二分,对于每一个元素,记录颜色和位置,对于两个关键字排序,颜色先,再位置。
对于1的操作,二分查找大于等于l的最小数,小于等于r的最大数。
对于2的操作,注意到位置不会有重复,所以每次修改只需修改二元组的位置,这样不会改变其相对位置。
这二分打得好不爽啊,还有7788得判断。
还有就是为什么有些用STL的跑得比我手打的二分查找还快啊,蒟蒻我只能以泪洗面。
代码:
//2017.11.2 //二分 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read(); int Max(int x,int y){return x>y?x:y;} int Min(int x,int y){return x<y?x:y;} namespace lys{ ; struct cntcol{ int num; int col; }co[N]; int f1[N],f2[N],a[N]; int n,m; bool cmp(const cntcol &x,const cntcol &y){ if(x.col<y.col) return true ; if(x.col>y.col) return false ; if(x.num<y.num) return true ; return false ; } int main(){ int i,opt,x,y,z,l,r,mid,s,t; n=read(); m=read(); ;i<=n;i++) co[i].col=read(),co[i].num=i,a[i]=co[i].col; sort(co+,co++n,cmp); ;i<=n;i++){ if(!f1[co[i].col]) f1[co[i].col]=i; f2[co[i].col]=i; } while(m--){ opt=read(); ){ x=read(); y=read(); z=read(); l=f1[z],r=f2[z]; ){ puts("); continue ; } while(l<r){ mid=(l+r)>>; if(co[mid].num>=x) r=mid; ; } s=l; if(co[s].num>y){ puts("); continue ; } l=f1[z],r=f2[z]; while(l<r){ mid=(l+r+)>>; ; else l=mid; } t=l; if(co[t].num<x){ puts("); continue ; } printf(); } ){ x=read(); ]) continue ; l=f1[a[x]],r=f2[a[x]]; while(l<r){ mid=(l+r)>>; if(co[mid].num>=x) r=mid; ; } co[l].num=x+; l=f1[a[x+]],r=f2[a[x+]]; while(l<r){ mid=(l+r)>>; )) r=mid; ; } co[l].num=x; int temp=a[x]; a[x]=a[x+]; a[x+]=temp; } } ; } } int main(){ lys::main(); ; } inline int read(){ ,ff=; char c=getchar(); '){ ; c=getchar(); } +c-',c=getchar(); return kk*ff; }
最新文章
- Oracle 违反协议 OALL8 处于不一致状态
- codevs 1001 舒适的路线(Kruskal)
- [LeetCode] Min Stack
- m=m++,结果让你大吃一惊。
- MySQL - 定时备份
- 创建下拉列表并通过ajax填充下拉数据
- maven 依赖冲突的问题
- 解读 《2014 最流行编程语言》 by Code Eval
- tp28xx port pin (open-drain )and (push-pull) 和open collector)
- Oracle基础(五):多表查询
- 6.Hibernate单向的多对一 关联映射
- luci 随笔
- Oracle 12cR1 RAC 在VMware Workstation上安装(上)—OS环境配置
- 【转】一分钟内检查Linux服务器性能
- django 1.10.3 admin后台管理设置显示中文
- 容器—stack
- oo第四次博客总结
- <;转载>;ford-fulkerson算法2
- P1168 中位数
- noip第16课资料