## T1 
维护区间最长连续上升序列，线段树端点合并，每个节点维护从左边开始的长度、最左边的值，以最右边结尾的长度、最右边的值，和最常上升序列的长度
```c++
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=100005;
using namespace std;
int lsum[maxn*4],rsum[maxn*4],sum[maxn*4],col[maxn*4],lnum[maxn*4],rnum[maxn*4];
int n,m,x,a,b,c;
char op[15];

void PushUp(int rt,int len)
{
    //默认
    lsum[rt]=lsum[rt*2];
    rsum[rt]=rsum[rt*2+1];
    sum[rt]=max(sum[rt*2],sum[rt*2+1]);
    //修改
    if(rnum[rt*2]<lnum[rt*2+1])//如果左区间的右端点大于右区间的左端点
    {
        if(lsum[rt]==len-len/2)
            lsum[rt]+=lsum[rt*2+1];
        if(rsum[rt]==len/2)
            rsum[rt]+=rsum[rt*2];
        sum[rt]=max(sum[rt],rsum[rt*2]+lsum[rt*2+1]);
    }
    //该区间的左端点等于该区间的左区间的左端点
    lnum[rt]=lnum[rt*2];
    //该区间的右端点等于该区间的右区间的右端点
    rnum[rt]=rnum[rt*2+1];
}
void PushDown(int rt,int len)
{
    //col[]=0代表不变，=c代表改变
    if(col[rt])
    {
        //左区间的左端点，左区间的右端点，左区间的标记
        lnum[rt*2]=rnum[rt*2]=col[rt*2]=col[rt];
        //右区间的右端点，右区间的右端点，右区间的标记
        lnum[rt*2+1]=rnum[rt*2+1]=col[rt*2+1]=col[rt];
        //初始化
        lsum[rt*2]=rsum[rt*2]=sum[rt*2]=1;
        lsum[rt*2+1]=rsum[rt*2+1]=sum[rt*2+1]=1;
        col[rt]=0;
    }
}
void Build(int l,int r,int rt)
{
    sum[rt]=lsum[rt]=rsum[rt]=1;
    col[rt]=0;
    if(l==r)
    {
        scanf("%d",&x);
        //改变的左端点和右端点
        rnum[rt]=lnum[rt]=x;
        return ;
    }
    int mid=(l+r)/2;
    Build(l,mid,rt*2);
    Build(mid+1,r,rt*2+1);
    PushUp(rt,r-l+1);
}
void Update(int L,int R,int c,int l,int r,int rt)
{
    //cout<<l<<" "<<r<<' '<<rt<<endl;
    if(L<=l && r<=R)
    {
        sum[rt]=lsum[rt]=rsum[rt]=1;
        lnum[rt]=rnum[rt]=col[rt]=c;
        return ;
    }
    PushDown(rt,r-l+1);
    int mid=(l+r)/2;
    if(L<=mid)
        Update(L,R,c,l,mid,rt*2);
    if(R>mid)
        Update(L,R,c,mid+1,r,rt*2+1);
    PushUp(rt,r-l+1);
}
int Query(int L,int R,int l,int r,int rt)
{
    if(L<=l && r<=R) return sum[rt];
    PushDown(rt,r-l+1);
    int mid=(l+r)/2;
    if(R<=mid)
        return Query(L,R,l,mid,rt*2);
    else if(L>mid)
        return Query(L,R,mid+1,r,rt*2+1);
    else
    {
        int left=Query(L,R,l,mid,rt*2);
        int right=Query(L,R,mid+1,r,rt*2+1);
        int ans=max(left,right);
        if(rnum[rt*2]<lnum[rt*2+1])
            ans=max(ans,min(rsum[rt*2],mid-L+1)+min(lsum[rt*2+1],R-mid));
        return ans;
    }
}
int main()
{
    //freopen("data1.in","r",stdin);
    scanf("%d%d",&n,&m);

    Build(1,n,1);
    while(m--)
    {
        //cout<<111<<endl;
        cin>>op;
        if(op[0]=='Q')
        {
            scanf("%d%d",&a,&b);
            printf("%d\r\n",Query(a,b,1,n,1));
        }
        else if(op[0]=='U')
        {
            scanf("%d%d%d",&a,&b,&c);
            Update(a,b,c,1,n,1);
        }
    }

    return 0;
}
```

## T2
   - 设 $s = a + b$，则 $s$ 的取值范围是 $[2l, r]$
   - 对于每个可能的 $s$，满足 $a + b = s$ 且 $a,b \ge l$ 的对数为：$s - 2l + 1$
   - 对所有可能的 $s$ 求和，得到总对数的公式：$\frac{(r - 2l + 1) \times (r - 2l + 2)}{2}$
```c++
#include <iostream>
using namespace std;

int main() {
    // 使用 long long 防止溢出（结果可能达到 1e18 级别）
    long long l, r;
    cin >> l >> r;
    
    long long min_sum = 2 * l;
    if (min_sum > r) {
        cout << 0 << endl;
    } else {
        long long n = r - min_sum + 1;
        // 等差数列求和：n*(n+1)/2，注意运算顺序避免溢出
        long long ans = n * (n + 1) / 2;
        cout << ans << endl;
    }
    
    return 0;
}
```

## T3
筛法筛出所有质数，暴力求任意两个质数之间的距离，然后跑最短路
```c++
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
bool pr[10003],vis[10003];
int a,b,t,i,j;
struct node
{
    int a,step;
}p,q;
void pri()
{
    memset(pr,-1,sizeof(pr));
    pr[0]=pr[1]=0;
    for(i=2; i<10003; i++)
    {
        if(pr[i])
            for(j=2*i; j<10003; j+=i)
                pr[j]=0;
    }
}
int change(int x,int i,int j)
{//方便改变数字的每一位，x是原数字，i代表第几位i=1是个位，j是改编成几（0————9，千位不能为0）
    if(i==1) return (x/10)*10+j;
    else if(i==2) return (x/100)*100+x%10+j*10;
    else if(i==3) return (x/1000)*1000+x%100+j*100;
    else if(i==4) return (x%1000)+j*1000;
}
void bfs()//简单bfs
{
    queue<node>que;
    p.a=a;
    p.step=0;
    vis[a]=1;
    que.push(p);
    while(!que.empty())
    {
        p=que.front();
        que.pop();
        q.step=p.step+1;
        for(i=1; i<5; i++)
            for(j=0; j<10; j++)
            {
                if(i==4&&j==0)
                    continue;
                q.a=change(p.a,i,j);
                if(q.a==b)
                {
                    printf("%d\n",q.step);
                    return;
                }
                if(pr[q.a]&&!vis[q.a])
                {
                    que.push(q);
                    vis[q.a]=1;
                }
            }
    }
    printf("Impossible\n");
}
int main()
{
    pri();//素数筛初始化
    scanf("%d",&t);
    while(t--)
    {
        memset(vis,0,sizeof(vis));//初始化
        scanf("%d %d",&a,&b);
        if(a==b){printf("0\n");continue;}//a==b情况单独处理；
        bfs();
    }
    return 0;
}
```

## T4
设$f_i$为前i只猫的最大效率   
$$
f_i = f_j+sum_i-sum_{j+1}
$$
单调队列优化的板子题(好像暴力 也能过)
```c++

#include<iostream>
#include<climits>
using namespace std;

int n,k;
long long int sum[100005];
long long int dp[100005];
int que[100005];
long long int cow[100005];
int front=1,back=1;

int main(int argc, const char * argv[])
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>cow[i];
        sum[i]=cow[i]+sum[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        while(front<=back && dp[i-1]-sum[i]>=dp[que[back]-1]-sum[que[back]]) back--;
        que[++back]=i;
        while(front<=back && que[front]<i-k) front++;
        int j = que[front]; 
        dp[i]=dp[j-1]+sum[i]-sum[j];
    }
    cout<<dp[n]<<endl;
    return 0;
}
```

## T5
直接模拟
```c++
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
string str;
int main()
{
    cin>>str;
    int win_a=0,win_b=0;
    int sum_a=0,sum_b=0;
    int top = 1;
    for(int i=0;str[i]!='\0';i++){
        if(str[i]=='E')break;
        if(str[i]=='A')sum_a++;
        if(str[i]=='B')sum_b++;
        if(top<5 && sum_a>=25 && sum_a>sum_b && sum_a-sum_b>=2){
            win_a++;
            top++;
            sum_a=0;
            sum_b=0;
        }
        if(top<5 && sum_b>=25 && sum_a<sum_b && sum_b-sum_a>=2){
            win_b++;
            top++;
            sum_a=0;
            sum_b=0;
        }
        if(top==5 && sum_a>=15 && sum_a>sum_b && sum_a-sum_b>=2){
            win_a++;
            top++;
            sum_a=0;
            sum_b=0;
        }
        if(top==5 && sum_b>=15 && sum_b>sum_a && sum_b-sum_a>=2){
            win_b++;
            top++;
            sum_a=0;
            sum_b=0;
        }
        if(top>5)break;
    }
    cout<<win_a<<':'<<win_b<<endl;
    return 0;
}
```