周赛round36

E

构造一张图，让左上角到右下角的最短路不是把所有点都走一遍，也不是长度为n+m-2（一直向下或向右），并且不存在绝对众数（某个字母出现次数大于总数一半）

由于是构造题，不止一种思路。我开始想的是一种比较麻烦的，不过最后也过了。就是类似样例里的那种走法，先一直往下，再一直往右，直到(n,m-1)，往上拐一个小圈到达(n,m)，这样路径长度为n+m。为了保证只有这一种走法，把这条路径的边上都用封住。剩余格子只要保证别出现绝对众数就可以了，那么可以每次都放出现次数最小的。

using namespace std;
const int N=1e3+10;
int a[N][N];
int cnt[15];
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
int main(){
    int n,m;
    cin>>n>>m;
    int t=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=-1;
        }
    }
    //先往下
    for(int i=1;i<=n;i++){
        a[i][1]=t++;
        cnt[a[i][1]]++;
        t%=15;
    }
    //再往右
    for(int j=2;j<=m-1;j++){
        a[n][j]=t++;
        cnt[a[n][j]]++;
        t%=15;
    }
    //最后拐一个小弯
    t--;
    if(t<0)t+=15;
    a[n][m]=t;
    a[n-1][m-1]=(t+1)%15;
    a[n-1][m]=(t+2)%15;
    cnt[a[n][m]]++;
    cnt[a[n-1][m-1]]++;
    cnt[a[n-1][m]]++;
    //持续统计各种字符出现次数
    
    for(int i=1;i<=n-1;i++){
        a[i][2]=a[i][1];
        cnt[a[i][2]]++;
    }
    for(int i=3;i<=m-2;i++){
        a[n-1][i]=a[n][i];
        cnt[a[n-1][i]]++;
    }//路径外面包一圈，用和左侧、下面相同的字符包
    //剩下的随便放，不出现绝对众数就行
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==-1){
                set<pair<int,int>>s;//判断出现次数最小的字符
                for(int k=0;k<15;k++){
                    s.insert({cnt[k],k});
                }
                a[i][j]=(*s.begin()).second;//放这种字符
                cnt[a[i][j]]++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<(char)(a[i][j]+'a');
        }
        cout<<'\n';
    }
}

官解比这个好很多，思路是先往右走到(1,m-1)，然后往下走到第二行，再往左走到(2,1)，然后一直往下到(n,1)，再往右到(n,m)。之所以走到(1,m-1)是为了防止路径长度变成nm-1（如果走到(1,m)的话，在n=m=3的样例中路径长度就变成nm-1了）。

为了保证只有这一种走法，开始让每一行都相同，均为a,b,c,d,a,b,c,d……的循环，由于相邻行相同，同一行内相邻元素不同，可以在一行内任意走，但是不能跨行。然后在(1,m-1)的位置开一个口子，允许从这里走到第二行，再开一条(2,1)到(n,1)的通路。在一个口子的做法就是统计一下该点相邻点都有哪些字符，然后把该点字符变成一个与相邻字符都不同的字符，这样就可以走到相邻点了

F 思维 树状数组

关键还是思维吧，没见过这种题的话确实想不出来。考场上还是要多观察性质，很多时候能不能推出来一些关键性质，往往决定了能不能做。

比如我在赛时就观察出来了，任意回文串，如果长度为偶，则一定包含形如aa的回文串，如果长度为奇，一定包含形如aba的回文串。但我的观察止步于此了，因此没做出来。

实际上，根据这个观察往后推，还有更关键的结论：可以先枚举一下满足要求的字符串应该长什么样子，太长的不好想，可以先想简单的。长度为2的，一定是两个不同的字符构成的，长度为三的，也一定是三个不同的字符构成的，那么长度为三的合法串实际上只有3!=6种，分别是red的全部排列。那么长度为4的呢？

以red为例，第四个不能是d，否则dd回文，不能是e，f否则ede回文，那么只能是r。类似地，可以发现所有长度为4的串，第四个字符一定和第一个相同。那么长度为5的呢？实际上，[2,4]构成的子串，是和长度为3类似的情况，那么类似地，第五个字符一定要和第二个字符相同。这样往下推，会发现所有合法串的第i个位置，一定和第i-3个位置相同，也就是说合法串都是循环的，周期为3。而长度为3的合法串只有6种，那么所有合法串也就只有6种模式。

那么，想把一个串变成合法串，就是要修改其中一些字符，使其变成这六种模式之一。变成合法串的最小代价，就是变成这六种模式的代价的最小值。具体来说，查询把[l,r]变成合法串需要的最小代价，就是[l,r]和合法模式的不同字符个数的最小值。

这实际上是一个前缀和区间查询，除此之外还要支持单点修改，那么可以用树状数组或者线段树。单点修改树状数组就可以，那么为了减少码量选择树状数组（区间修改区间查询必须用线段树）

using namespace std;
#define ll long long 
#define db double
#define ld long double
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define rep1(i,x,y) for(int i=(x);i>=(y);i--)
#define pii pair<int,int>
#define ls u<<1
#define rs u<<1|1
const int N=1e5+10;
const int M1=1e9+7,M2=998244353; 
int t[N][6];
string str[6]={"red","rde","dre","der","edr","erd"};
int lowbit(int x){
    return x&(-x);
}
void add(int x,int id,int k){
    while(x<=N){
        t[x][id]+=k;
        x+=lowbit(x);
    }
}
int ask(int x,int id){
    int ret=0;
    while(x>0){
        ret+=t[x][id];
        x-=lowbit(x);
    }
    return ret;
}
int ask(int l,int r,int id){
    int ret=ask(r,id);
    ret-=ask(l-1,id)；
    return ret;
}
string s;
void solve(void){
	int n,k;
    cin>>n>>k;
    cin>>s;
    s=' '+s;
    rep(i,1,n){
        rep(j,0,5){//对六种模式分别计算
            if(s[i]!=str[j][i%3]){//不相等，[1,i]内不同字符个数加1
                add(i,j,1);
            }
        }
    }
    rep(i,1,k){
        int op;
        cin>>op;
        if(op==1){
            int x;
            char c;
            cin>>x>>c;
            rep(j,0,5){
            	//原来就不等，对总数有贡献，那么修改后贡献需要减掉
                if(s[x]!=str[j][x%3])add(x,j,-1);
                //改完之后不等，有贡献，加上贡献
                if(c!=str[j][x%3])add(x,j,1);
            }
            s[x]=c;//保存修改，后面修改的时候要查
        }
        else{
            int l,r;
            cin>>l>>r;
            int ans=1e9;
            rep(j,0,5){//求变成六种合法模式的最小值
                ans=min(ans,ask(l,r,j));
            }
            cout<<ans<<'\n';
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int test=1;
//    cin>>test; 
    while(test--){
        solve();
    }
}