借一个入门题引入下线段树吧..其实我的树状数组区间修改区间查询还没更,也不太会...毕竟要死记推导也挺难的.
线段树是一种分治结构,我觉得是这样的,同时也是一颗二叉搜索树.它有几个代码,其中包括建树,修改,查询.和树状数组类似,线段树的懒标记就是你不要用的时候先保留,要用的时候再用.
就这些吧...好像说起来很简单...但是因为我写的太少了.然后导致我emmm..
拿这个题说吧,合并字符串的价值,还是感谢好心的不知名的大佬...确实挺简单的.
首先我们先预处理下A段,算下切A的每个位子和B一起的max_val.然后我们在用线段树维护区间最大值,什么最大值呢,就是在A段中的(l-r)切一刀的最大值,分治嘛,答案必定是(1-n)切一刀的最大值了.考虑每个B对于答案的影响.怎么考虑呢,开始的B都是在A后面那段对吧,现在我来了一个B对于区间的影响是什么呢?来了一个B,我前面那段会增加这个字母,我后面那段会减少这个字母.那么它影响的区间是什么呢.假定我统计了A中每个字母在某种数量下的位子.对于增加来说只有当下面切割B的数量不超过一半才行对吧,然后区间肯定是从1到剩余一半的位子对吧= - =.-1的情况同理,把区间max维护下就好了/(0,0)
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{
    int l,r,ans;//区间的左右边间以及区间max的ans.
}tree[N<<2];

char a[N],b[N];
int num[4],lazy[N<<2];
int pos[4][N];//记录下是第几个字母数量是多少的在哪个位子.
int tot[4];//统计下没种字母有多少个.
int it[N],nw[4];//预处理A记录max_val,记录下B到i的数量.

void build(int l,int r,int u)
{
    tree[u].l=l,tree[u].r=r;
    if(l==r)
    {
        tree[u].ans=it[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,u<<1);
    build(mid+1,r,u<<1|1);
    tree[u].ans=max(tree[u<<1].ans,tree[u<<1|1].ans);
}

void change(int u,int val)
{
    tree[u].ans+=val;
    lazy[u]+=val;
    return;
}

void modify(int l,int r,int L,int R,int u,int val)
{
    if(L<=l&&r<=R)
    {
        change(u,val);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)  modify(l,mid,L,R,u<<1,val);
    if(mid<R)   modify(mid+1,r,L,R,u<<1|1,val);
    tree[u].ans=max(tree[u<<1].ans,tree[u<<1|1].ans)+lazy[u];
}

int C(char x)
{
    if(x=='A') return 0;
    if(x=='C') return 1;
    if(x=='G') return 2;
    if(x=='T') return 3;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int ans=0;
        memset(lazy,0,sizeof lazy);
        memset(pos,0,sizeof pos);
        memset(tot,0,sizeof tot);
        memset(num,0,sizeof num);
        memset(nw,0,sizeof nw);
        memset(it,0,sizeof it);
        memset(tree,0,sizeof tree);
        scanf("%s",a+1);int n=strlen(a+1);
        scanf("%s",b+1);int m=strlen(b+1);
        for(int i=1;i<=n;i++)
        {
            int x=C(a[i]);
            tot[x]++;
        }
        for(int i=1;i<=m;i++)
        {
            int x=C(b[i]);
            tot[x]++;
        }
        for(int i=1;i<=n;i++)//以这个点做切分.
        {
            int x=C(a[i]);
            pos[x][++num[x]]=i;
            for(int j=0;j<=3;j++)
            {
                it[i]+=min(num[j],tot[j]-num[j]);
            }
        }
        build(0,n,1);ans=max(ans,tree[1].ans);//建好树.
        //cout<<tree[1].ans<<endl;
        for(int i=1;i<=m;i++)//分配B的刀.
        {
            int x=C(b[i]),ps;
            nw[x]++;
            int p=tot[x]/2-nw[x]+1;
            if(p>0)//假如它*2<=总数,是可以更新的,区间+1.
            {
                if(p>num[x]) ps=n;
                else         ps=pos[x][p]-1;
                modify(0,n,0,ps,1,1);
            }
            p=(tot[x]+1)/2-nw[x]+1;
            if(p<=num[x])
            {
                if(p>0)     ps=pos[x][p];
                else        ps=0;
                modify(0,n,ps,n,1,-1);
            }
            ans=max(ans,tree[1].ans);
        }
        printf("%d\n",ans);
    }
    return 0;
}

还是有很多很多的细节- -wa了一会,对着标程改了下,明天想想为什么吧,困了...好菜,线段树好难写啊