洛谷CF1473D

分析
题意：给定l,r，将1~l-1的符号于r+1~n的符号合并。
从左往右依次计算，求过程中最大值与最小值的差+1。
For example:
n=4 l=2 r=3 符号串为+-+-
则依次进行“+”“-”运算，原来为0，+1后为1，-1后为0
其中最大值为1，最小值为0，故输出2
算法
因n较大，考虑倍增算法。
用st表储值（f[i][j]中mx表示i~i+（1<<j)-1的最大值，mn表示最小值，sum表示当前数值）
对于每一次询问，我们可以先处理1~l-1段（O（log n)),再处理r+1~n段（O（log n))
时间复杂度(O(n log n+m log n))
AC Code
#include<bits/stdc++.h>
using namespace std;
struct xx{int mx,mn,sum;}f[200005][25];
int t,i,j,n,m,l,r;
int main(){
　　scanf("%d",&t);
　　while(t--){
　　　　scanf("%d%d\n",&n,&m);
　　　　for(i=1;i<=n;i++){
　　　　　　char ch=getchar();
　　　　　　if(ch=='-')f[i][0].mx=f[i][0].mn=f[i][0].sum=-1;
　　　　　　else f[i][0].mx=f[i][0].mn=f[i][0].sum=1;
　　　　}
　　　　for(i=1;i<=log2(n)+1;i++)
　　　　for(j=1;j+(1<<i)-1<=n;j++){
　　　　　　f[j][i].mx=max(f[j][i-1].mx,f[j][i-1].sum+f[j+(1<<(i-1))][i-1].mx);
　　　　　　f[j][i].mn=min(f[j][i-1].mn,f[j][i-1].sum+f[j+(1<<(i-1))][i-1].mn);
　　　　　　f[j][i].sum=f[j][i-1].sum+f[j+(1<<(i-1))][i-1].sum;
　　　　}//较为简单的st表预处理
　　　　for(i=1;i<=m;i++){
　　　　　　scanf("%d%d",&l,&r);
　　　　　　int now=1,last=0,maxx=0,minn=0;//last表示上一次运算完的结果，maxx表示最大值，minn表示最小值
　　　　　　for(j=log2(n)+1;j>=0;j--){
　　　　　　　　if(now+(1<<j)<l){
　　　　　　　　　　maxx=max(maxx,last+f[now][j].mx);
　　　　　　　　　　minn=min(minn,last+f[now][j].mn);
　　　　　　　　　　last+=f[now][j].sum;
　　　　　　　　　　now+=(1<<j);
　　　　　　　　}//倍增跳跃到下一个点
　　　　　　}
　　　　　　if(now<l){maxx=max(maxx,last+f[now][0].mx);minn=min(minn,last+f[now][0].mn);last+=f[now][0].sum;}//处理1~l-1段
　　　　　　now=r+1;
　　　　　　for(j=log2(n)+1;j>=0;j--){
　　　　　　　　if(now+(1<<j)<=n){
　　　　　　　　　　maxx=max(maxx,last+f[now][j].mx);
　　　　　　　　　　minn=min(minn,last+f[now][j].mn);
　　　　　　　　　　last+=f[now][j].sum;
　　　　　　　　　　now+=(1<<j);
　　　　　　　　}//倍增跳跃到下一个点
　　　　　　} 
　　　　　　if(now<=n){maxx=max(maxx,last+f[now][0].mx);minn=min(minn,last+f[now][0].mn);last+=f[now][0].sum;}//处理r+1~n段
　　　　　　printf("%d\n",maxx-minn+1);
　　　　}
　　}
}