cojR14

Source

commetoj R14

好题:E 飞翔的小鸟

一直复制题解链接……

C 序列

来自看题小王子的提示:第i次修改是修改成i

请先思考后再展开

题目等价于求每个操作前缀,操作子集的不同段个数,转化为不同断点个数+1

分别考虑每个区间两端点作为断点的贡献=$2^{n-1-后面跨过的区间数}$

仅给出暴力,写个线段树就能优化成$O(n^2logn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pr oper[N];
void main()
{
int n=qread(),m=qread();
fo(tim,1,m)
{
int l=qread(),r=qread();oper[tim]=MP(l,r);
ll ans=qpower(2,tim);
fo(i,1,tim)
{
int sum;
if(oper[i].FR!=1){sum=0;fo(j,i+1,tim) if(oper[j].FR<=oper[i].FR and oper[i].FR-1<=oper[j].SE) sum++;ans+=qpower(2,tim-sum-1);}
if(oper[i].SE!=n){sum=0;fo(j,i+1,tim) if(oper[j].FR<=oper[i].SE+1 and oper[i].SE<=oper[j].SE) sum++;ans+=qpower(2,tim-sum-1);}
ans%=MOD;
}write2((ans+MOD)%MOD);
}
}

题解的优秀做法暴力做就是$O(n^2)$,复杂度下界为nlogn

D 转转的数据结构题

请先思考后再展开

很自然的思路是离线后,将一个前缀的操作处理完,然后回答右端点在这里的询问

注意到是赋值操作,所以一个位置如果被后面的覆盖,那么以后的这里的值都跟以前操作无关了,所以如果我们能维护若干个互不重叠的线段,那么回答询问就是回答其中时间戳在一段后缀的线段权值和

注意到这些线段始终是互不重叠的,那么每次加入暴力地去删除来维护,因为每次只添加一段线段所以复杂度肯定是对的,因为是覆盖也很好写,支持回答询问写个树状数组就行了,$O(nlogn+nlogn)$

E 飞翔的小鸟

题解

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/f88a2275.html
转载请注明出处,谢谢!