2020-2021:teams:wangzai_milk:codeforces_round_654_div._2_zars19
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:codeforces_round_654_div._2_zars19 [2020/07/17 22:00] zars19 创建 |
2020-2021:teams:wangzai_milk:codeforces_round_654_div._2_zars19 [2020/07/18 01:30] (当前版本) zars19 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | A. Magical Sticks | + | ====== A. Magical Sticks ====== |
| 有 $1 \le i \le n$ 的小棍各一根。问能变成相同长度的小棍最多多少根。 | 有 $1 \le i \le n$ 的小棍各一根。问能变成相同长度的小棍最多多少根。 | ||
| 行 22: | 行 22: | ||
| } | } | ||
| </code></hidden> | </code></hidden> | ||
| + | \\ | ||
| - | B. Magical Calendar | + | ====== B. Magical Calendar ====== |
| 一周可以有 $1$ 至 $r$ 天，在格子日历上涂色连续 $n$ 天（要求形状是联通的），问可以有多少形状 | 一周可以有 $1$ 至 $r$ 天，在格子日历上涂色连续 $n$ 天（要求形状是联通的），问可以有多少形状 | ||
| 行 48: | 行 49: | ||
| } | } | ||
| </code></hidden> | </code></hidden> | ||
| + | \\ | ||
| - | C. A Cookie for You | + | ====== C. A Cookie for You ====== |
| 小甜饼， $a$ 个香草味， $b$ 个巧克力味。 $n$ 个第一种客人，香草味严格多时吃香草，否则吃巧克力。 $m$ 个第二种客人，香草味严格多时吃巧克力，否则吃香草。能否安排顺序使得每个顾客吃个小甜饼。 | 小甜饼， $a$ 个香草味， $b$ 个巧克力味。 $n$ 个第一种客人，香草味严格多时吃香草，否则吃巧克力。 $m$ 个第二种客人，香草味严格多时吃巧克力，否则吃香草。能否安排顺序使得每个顾客吃个小甜饼。 | ||
| 行 74: | 行 76: | ||
| } | } | ||
| </code></hidden> | </code></hidden> | ||
| + | \\ | ||
| - | D. Grid-00100 | + | ====== D. Grid-00100 ====== |
| 构造 $n\times n~01$ 矩阵，最小化 $f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2$ 其中 $R,C$ 分别是行、列元素的和。 | 构造 $n\times n~01$ 矩阵，最小化 $f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2$ 其中 $R,C$ 分别是行、列元素的和。 | ||
| 行 117: | 行 120: | ||
| } | } | ||
| </code></hidden> | </code></hidden> | ||
| + | \\ | ||
| - | E1. Asterism (Easy Version) | + | ====== E1. Asterism (Easy Version) ====== |
| 给定数组 $a_i$ ，可以指定一个排列作为顺序。Yuzu有一个数 $x$ ， $x\ge a_i$ 的情况下才能打过第 $i$ 关，并且进入下一关时 $x$ 增加 $1$ 。 $f(x)$ 表示初始数字 $x$ 时有多少种排列Yuzu能打完所有关卡 $n$ 。问有多少 $f(x)$ 不能被素数 $p$ 整除，输出这些数字。 | 给定数组 $a_i$ ，可以指定一个排列作为顺序。Yuzu有一个数 $x$ ， $x\ge a_i$ 的情况下才能打过第 $i$ 关，并且进入下一关时 $x$ 增加 $1$ 。 $f(x)$ 表示初始数字 $x$ 时有多少种排列Yuzu能打完所有关卡 $n$ 。问有多少 $f(x)$ 不能被素数 $p$ 整除，输出这些数字。 | ||
| 行 132: | 行 136: | ||
| $f(x)=\prod_1^nb_{x+i-1}-(i-1)$ | $f(x)=\prod_1^nb_{x+i-1}-(i-1)$ | ||
| - | E2. Asterism (Hard Version) | + | ====== E2. Asterism (Hard Version) ====== |
| 数据范围增大后不能再暴力计算。但观察一下可以发现在上述有效范围内如果 $f(x_0)$ 可以被整除，那对于 $x > x_0,f(x)$ 也可以被整除。于是就可以二分一下位置。 | 数据范围增大后不能再暴力计算。但观察一下可以发现在上述有效范围内如果 $f(x_0)$ 可以被整除，那对于 $x > x_0,f(x)$ 也可以被整除。于是就可以二分一下位置。 | ||
| 行 172: | 行 176: | ||
| } | } | ||
| </code></hidden> | </code></hidden> | ||
| + | \\ | ||
| + | |||
| + | ====== F. Raging Thunder ====== | ||
| + | |||
| + | 认真读题之后发现其实是给出一个左右串，每次反转（左变右右变左）一个区间查询> > > < < < < <形状最长长度。 | ||
| + | |||
| + | 很明显线段树+lazy tag，维护> > < <形状最长长度、< < < > >形状最长长度、左右两边的两种形状长度、左右两边<和>的长度。 | ||
| + | |||
| + | <hidden><code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | using namespace std; | ||
| + | const int N=5e5+10; | ||
| + | char s[N]; | ||
| + | struct Node | ||
| + | { | ||
| + | int lR,lL,rL,rR,maxn,tmaxn,lz,sz,lmaxn,rmaxn,ltmaxn,rtmaxn; | ||
| + | }t[N*4]; | ||
| + | Node combine(Node a,Node b) | ||
| + | { | ||
| + | Node x; | ||
| + | x.lR=a.lR; | ||
| + | if(x.lR==a.sz)x.lR+=b.lR; | ||
| + | x.lL=a.lL; | ||
| + | if(x.lL==a.sz)x.lL+=b.lL; | ||
| + | x.rR=b.rR; | ||
| + | if(x.rR==b.sz)x.rR+=a.rR; | ||
| + | x.rL=b.rL; | ||
| + | if(x.rL==b.sz)x.rL+=a.rL; | ||
| + | x.maxn=max(max(a.maxn,b.maxn),max(a.rmaxn+b.lL,a.rR+b.lmaxn)); | ||
| + | x.tmaxn=max(max(a.tmaxn,b.tmaxn),max(a.rtmaxn+b.lR,a.rL+b.ltmaxn)); | ||
| + | x.lmaxn=a.lmaxn; | ||
| + | if(x.lmaxn==a.sz)x.lmaxn+=b.lL; | ||
| + | if(a.lR==a.sz)x.lmaxn=max(x.lmaxn,a.sz+b.lmaxn); | ||
| + | x.ltmaxn=a.ltmaxn; | ||
| + | if(x.ltmaxn==a.sz)x.ltmaxn+=b.lR; | ||
| + | if(a.lL==a.sz)x.ltmaxn=max(x.ltmaxn,a.sz+b.ltmaxn); | ||
| + | x.rmaxn=b.rmaxn; | ||
| + | if(x.rmaxn==b.sz)x.rmaxn+=a.rR; | ||
| + | if(b.rL==b.sz)x.rmaxn=max(x.rmaxn,b.sz+a.rmaxn); | ||
| + | x.rtmaxn=b.rtmaxn; | ||
| + | if(x.rtmaxn==b.sz)x.rtmaxn+=a.rL; | ||
| + | if(b.rR==b.sz)x.rtmaxn=max(x.rtmaxn,b.sz+a.rtmaxn); | ||
| + | x.sz=a.sz+b.sz,x.lz=0; | ||
| + | return x; | ||
| + | } | ||
| + | void build(int idx,int l,int r) | ||
| + | { | ||
| + | if(l==r) | ||
| + | { | ||
| + | t[idx].rR=t[idx].lR=(s[l]=='>'); | ||
| + | t[idx].rL=t[idx].lL=(s[l]=='<'); | ||
| + | t[idx].maxn=t[idx].tmaxn=t[idx].lmaxn=t[idx].rmaxn=t[idx].ltmaxn=t[idx].rtmaxn=1; | ||
| + | t[idx].sz=1,t[idx].lz=0; | ||
| + | return; | ||
| + | } | ||
| + | int mid=(l+r)>>1; | ||
| + | build(idx<<1,l,mid),build(idx<<1|1,mid+1,r); | ||
| + | t[idx]=combine(t[idx<<1],t[idx<<1|1]); | ||
| + | } | ||
| + | void rev(int idx) | ||
| + | { | ||
| + | t[idx].lz^=1; | ||
| + | swap(t[idx].lL,t[idx].lR),swap(t[idx].rR,t[idx].rL),swap(t[idx].maxn,t[idx].tmaxn); | ||
| + | swap(t[idx].lmaxn,t[idx].ltmaxn),swap(t[idx].rmaxn,t[idx].rtmaxn); | ||
| + | } | ||
| + | void pushdown(int idx) | ||
| + | { | ||
| + | if(!t[idx].lz)return; | ||
| + | t[idx].lz=0,rev(idx<<1),rev(idx<<1|1); | ||
| + | } | ||
| + | void change(int idx,int l,int r,int a,int b) | ||
| + | { | ||
| + | if(a<=l&&b>=r){rev(idx);return;} | ||
| + | pushdown(idx); | ||
| + | int mid=(l+r)>>1; | ||
| + | if(b<=mid)change(idx<<1,l,mid,a,b); | ||
| + | else if(a>mid)change(idx<<1|1,mid+1,r,a,b); | ||
| + | else change(idx<<1,l,mid,a,b),change(idx<<1|1,mid+1,r,a,b); | ||
| + | t[idx]=combine(t[idx<<1],t[idx<<1|1]); | ||
| + | } | ||
| + | Node query(int idx,int l,int r,int a,int b) | ||
| + | { | ||
| + | if(a<=l&&b>=r)return t[idx]; | ||
| + | pushdown(idx); | ||
| + | int mid=(l+r)>>1; | ||
| + | if(b<=mid)return query(idx<<1,l,mid,a,b); | ||
| + | else if(a>mid)return query(idx<<1|1,mid+1,r,a,b); | ||
| + | else return combine(query(idx<<1,l,mid,a,b),query(idx<<1|1,mid+1,r,a,b)); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n,q; | ||
| + | scanf("%d%d%s",&n,&q,s+1); | ||
| + | build(1,1,n); | ||
| + | for(int i=1;i<=q;i++) | ||
| + | { | ||
| + | int l,r; | ||
| + | scanf("%d%d",&l,&r); | ||
| + | change(1,1,n,l,r); | ||
| + | printf("%d\n",query(1,1,n,l,r).maxn); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| + | \\ | ||
2020-2021/teams/wangzai_milk/codeforces_round_654_div._2_zars19.1594994454.txt.gz · 最后更改: 2020/07/17 22:00 由 zars19
