•【题目描述】

有一个湖，他的周围都是城市，每个城市都只和他相邻的两个城市有道路相连。假设有n个城市，编号1-n，公路是双向的，公路有时候是好的，有时候是坏的，现在询问你两个城市是否可以互相到达。

•【输入格式】

第一行两个数，一个2<=n<=100000  和 1<=m<=100000，分别代表城市数目和询问次数；

接下来m行，每一行三个数f，a，b。f=0时，如果公路a，b之间的道路之前是好的，现在就变成坏的，如果之前是坏的，现在就变成好的。f=1时，询问a，b两个城市是否可以互相到达。

•【输出格式】

对于每一个f=1的询问，能到达输出“YES”，否则输出"NO".

思路如下：

首先，我们可以设g[x]数组表示x号城市与x+1号城市之间的道路好坏情况：g[x]=1时表示坏，g[x]=0时表示好，同时设sz为坏的道路的个数。

因为所有城市围起来形成一个圆，规定x到（x+1）号城市为顺时针方向，x到（x-1）号城市为逆时针方向。

我们来谈谈f=1时，即判断a、b两城市是否可以到达（预处理使a<b）。

那么在判断a、b两城市是否可以到达时，我们只需考虑两种情况：

（1）：沿顺时针道路判断是否可以到达

令G=g[a]+g[a+1]+g[a+2]+……+g[b-1]（即a沿顺时针到b间的路径间坏的道路的个数）很明显，我们只需判断G是否>=1。若是，则表示a沿顺时针到b之间的路径有坏的道路，不能从a顺时针到达b。

（2）：沿逆时针道路判断是否可以到达

其实思路也不难想出，我们可以简单地处理出sz（即坏的道路的个数），若sz-G=0，

即表示除a沿顺时针到b的路径间坏的道路外，没有坏的道路，这就等同于a沿逆时针到b的路径间没有坏的道路，可以从a到b。

反之（sz-G不为0）则表示a沿逆时针到b之间的路径有坏的道路，不能从a顺时针到达b。

好了，现在你已经了解了这题的大致思路了，那么就尝试AC吧！！！（不是

以上思路大家肯定都想到了（所以以上都是废话），那么我们开始优化时间吧！

我们懂得，若按照以上思路暴力求解，那么时间复杂度为O(nm)，只能拿到50pts

接下来考虑100pts算法

我们可以发现g是一维数组，求G为g的区间求和，那么很自然的就联想到树状数组

设树状数组f[x]表示坏的道路的个数， G=g[a]+g[a+1]+g[a+2]+…… +g[b-1] =求和f(b-1)-求和f(a-1）

然后1与n号城市间的道路做个特殊处理。

最后推荐大家参考代码理解（COGS代码已开放）

Over!!!

裸裸的区间DP。

我们定义f[l][r] 为卖掉l到r之间的临时得到的最大收益。

n[x]为第x个物品的价值。

Cl为第几天出售

转移方程就应该是f[l][r]=max(f[l+1][r]+cl*n[l],f[l][r+1]+cl*n[r]);

最后附上代码）

题目要求最大，观察数据范围，结合经验，考虑贪心。

当我们现在的烤鸡翅数量大于需求时，直接卖出。

否则，寻找前面已经卖出的最大的数量，如果该数大于当前需求，则用当前数目替代该数。

正确性不难证明：根据这个方法，我们遍历到第 $i$ 个人时，已经保证在不影响卖出人数的情况下让卖出的鸡翅数量最少。

再往后遍历时，也仍然可以保证。

这样，就实现了局部最优解向整体最优解的转变。

这个过程可以用大根堆实现。

子任务1：测试点$1\sim 3$

$1\leq k\leq n\leq15$，显然可以使用搜索法。

枚举所有括号序列，判断其是否合法。

  1、连续的*不能超过k个。

  2、括号要匹配。

  3、SAS类型是非法括号序列。

时间复杂度O($N\times 3^N$),预计得分15分。

ps:可直接跳到子任务4。

子任务2：测试点$1\sim 13$

显然是一道区间DP问题。

首先明确，合法的括号序列应该是(),(S),(A),(SA),(AS),AA,ASA。

定义$d(l,r)$表示区间$[l,r]$的子串是合法括号序列的方案数。通过观察可以发现，$d(l,r)$可以由S序列转移得到，因此需要定义额外的状态，定义$s(l,r)$表示区间$[l,r]$能否构成合法的S型。

那么对于(),(S),(A),(SA),(AS)型，显然有：

 $d(l,r)=1$, ()型

 $d(l,r)+=1$, (S)型,$s(l+1,r-1)=1$

 $d(l,r)+=d(l+1,r-1)$, (A)型

 $d(l,r)+=d(l+tk+1,r-1)$, (SA)型,$1\leq tk\leq k,s(l+1,l+tk)=1$

 $d(l,r)+=d(l+1,r-tk-1)$, (AS)型,$1\leq tk\leq k,s(r-tk,r-1)=1$

对于AA、ASA型，需要枚举中间的分隔点$j(l\leq j\leq r)$：

 $d(l,r)+=d(l,j)*d(j+1,r)$, (AA)型

 $d(l,r)+=d(l,j)*d(j+tk+1,r)$, (ASA)型,$1\leq tk\leq k,s(j+1,j+tk)=1$

但是，对于部分括号序列，会出现重复计数，例如()()()会被识别成A|AA或者AA|A，()*()*()会被识别成AS|ASA或ASA|S|A。

为了避免重复计数，要求在合并时只能合并一次，因此定义状态$a(l,r)$表示单独的A类型，也即(),(S),(A),(SA),(AS)型，这些类型的特点是不能拆分。因此，状态转移方程需要做出如下修改：

 $a(l,r)=d(l,r)$,(),(S),(A),(SA),(AS)型

对于AA,ASA型，这是出现重复计数的类型：

 $d(l,r)+=a(l,j)*d(j+1,r)$, (AA)型

 $d(l,r)+=a(l,j)*d(j+tk+1,r)$, (ASA)型,$1\leq tk\leq k,s(j+1,j+tk)=1$

综上，算法的流程如下：

 1、预处理得出所有的$s(l,r)$。

 2、从小到大依次枚举每个区间$[l,r]$，求出相应的$d(l,r)$。

 3、最终的答案即为$d(1,n)$。

注意：在运算过程中需要不断对$10^9+7$取余。

注意：通过观察可以得出，首字符必是(，尾字符必是)，可以进行特殊处理。

时间复杂度O($N^4$)，预计得分65分。

子任务3：测试点$1\sim 15$

对于测试点$14\sim 15$,字符串中仅含？。那么状态$d(l_1,r_1+k)$和$d(l_2,r_2+k)$虽然表示的区间不同，但是结果必然是相同的。

因此，定义状态$f(i)$表示$i$个？构成的合法的序列的方案数。那么，状态转移方程修改为：

$f(1)=0$,一个?

$f(2)=1$,()型

$f(i)+=1$,(S)型

$f(i)+=f(i-2)$,(A)型

$f(i)=f(i-2-tk)$,(AS),(SA)型,$1\leq tk\leq k$

$f(i)=f(j)*f(i-j)$,AA型，$2\leq j\leq i - 2$

$f(i)=f(j)*f(i-j-tk)$,ASA型，$2\leq j\leq i-2,1\leq tk\leq k$

同样，也需要考虑重复计数的问题，定义$g(i)$表示单独的A类型的方案数。

那么状态转移方程需要做出部分修改：

$g(i)=f(i)$,()(S)(A)(SA)(AS)型

$f(i)=g(j)*f(i-j)$,AA型，$2\leq j\leq i - 2$

$f(i)=g(j)*f(i-j-tk)$,ASA型，$2\leq j\leq i-2,1\leq tk\leq k$

时间复杂度：O($N^3$),预计得分75分。

子任务4：测试点$1\sim 20$

显然是一道区间DP问题。

首先明确，合法的括号序列应该是(),(S),(A),(SA),(AS),AA,ASA。

定义$d(l,r)$表示区间$[l,r]$的子串是合法括号序列的方案数。通过观察可以发现，$d(l,r)$可以由非法括号序列转移得到，因此需要定义额外的状态。

  定义$s(l,r)$表示区间$[l,r]$能否构成合法的S型。

  定义$sa(l,r)$表示区间$[l,r]$的子串是SA型的方案数。

  定义$as(l,r)$表示区间$[l,r]$的子串是AS型的方案数。

那么对于(),(S),(A),(SA),(AS)型，显然有：

  $d(l,r)=1$, ()型

  $d(l,r)+=s(l+1,r-1)$, (S)型

  $d(l,r)+=d(l+1,r-1)$, (A)型

  $d(l,r)+=sa(l+1,r-1)$, (SA)型

  $d(l,r)+=as(l+1,r-1)$, (AS)型

对于AA、ASA型，需要枚举中间的分隔点$j(l\leq j\leq r)$：

  $d(l,r)+=d(l,j)*d(j+1,r)$, (AA)型

  $d(l,r)+=d(l,j)*sa(j+1,r)$, (ASA)型

同时需要维护AS,SA型，同样需要枚举中间的分隔点$j(l\leq j\leq r)$：

  $as(l,r)+=d(l,j)*s(j+1,r)$, (AS)型

  $sa(l,r)+=s(l,j)*d(j+1,r)$, (SA)型

但是，对于部分括号序列，会出现重复计数，例如()()()会被识别成A|AA或者AA|A，()*()*()会被识别成AS|ASA或ASA|S|A。

为了避免重复计数，要求在合并时只能合并一次，因此定义状态$a(l,r)$表示单独的A类型，也即(),(S),(A),(SA),(AS)型，这些类型的特点是不能拆分。

因此，状态转移方程需要做出如下修改：

  $a(l,r)=d(l,r)$,(),(S),(A),(SA),(AS)型

对于AA,ASA型，这是出现重复计数的类型：

  $d(l,r)+=a(l,j)*d(j+1,r)$, (AA)型

  $d(l,r)+=a(l,j)*sa(j+1,r)$, (ASA)型

综上，算法的流程如下：

  1、预处理得出所有的$s(l,r)$。

  2、从小到大依次枚举每个区间$[l,r]$，求出相应的$d(l,r),a(l,r),sa(l,r),sa(l,r)$。

  3、最终的答案即为$d(1,n)$。

注意：在运算过程中需要不断对$10^9+7$取余。

注意：通过观察可以得出，首字符必是(，尾字符必是)，可以进行特殊处理。

时间复杂度O($N^3$)，预计得分100分。