T1
容易观察到，只有出现?io?时可能使用交换操作，其他情况可以被另外三个所取代，所以特判一下即可
然后还需要更新当前原字母的贡献，同时对其他三个操作各跑一次转移，力大砖飞即可
想打表也没人拦着你
#include<bits/stdc++.h>
#define N 100005
using namespace std;
char s[N];
int x[N],dp[N][10];
signed main(){int T;scanf("%d",&T);while(T--){scanf("%s",s+1);s[0]=' ';int n=strlen(s),ans=4;n--;for(int i=1;i<=n;i++){if(s[i]=='n')x[i]=1;else if(s[i]=='o')x[i]=2;else if(s[i]=='i')x[i]=3;else if(s[i]=='p')x[i]=4;else x[i]=0;}for(int i=0;i<=n;i++)for(int j=0;j<=4;j++)dp[i][j]=j;for(int i=1;i<=n;i++){if(x[i])dp[i][x[i]]=min(dp[i][x[i]],dp[i-1][x[i]-1]);if(i>=2&&x[i]==2&&x[i-1]==3)dp[i][3]=min(dp[i][3],dp[i-2][1]+1);for(int j=4;j;j--)dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);for(int j=1;j<=4;j++)dp[i][j]=min(dp[i][j],dp[i-1][j]+1);for(int j=1;j<=4;j++)dp[i][j]=min(dp[i][j],dp[i][j-1]+1);ans=min(ans,dp[i][4]);}printf("%d\n",ans);}return 0;
}
T2
考虑正难则反
显然的，正常情况下一个点无法被到达当且仅当它的上方和左方都有障碍
那么我们按照行数为第一关键字排序，列数为第二关键字排序，计算每一个有障碍的行有多少格子无法被抵达，需要线段树维护后缀有障碍的列数
同时需要对第一行或第一列有障碍的情况进行特判
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
struct Ty{int x,y;bool operator <(const Ty &a)const{if(x!=a.x)return x<a.x;else return y>a.y;}
}x[N];
vector<int>w[N];
int y[530000];
void update(int u,int l,int r,int id){if(l==r){y[u]=1;return;}int mid=(l+r)/2;if(id<=mid)update(u*2,l,mid,id);else update(u*2+1,mid+1,r,id);y[u]=y[u*2]+y[u*2+1];return;
}
int query(int u,int l,int r,int fl,int fr){if(l==fl&&r==fr)return y[u];int mid=(l+r)/2;if(fr<=mid)return query(u*2,l,mid,fl,fr);else if(fl>mid)return query(u*2+1,mid+1,r,fl,fr);else return query(u*2,l,mid,fl,mid)+query(u*2+1,mid+1,r,mid+1,fr);
}
signed main(){int n,m,k;scanf("%lld%lld%lld",&n,&m,&k);for(int i=1;i<=k;i++)scanf("%lld%lld",&x[i].x,&x[i].y);sort(x+1,x+k+1);for(int i=1;i<=k;i++)w[x[i].x].push_back(x[i].y);int ans=0,flag=0;if(w[1].size())for(int i=w[1][w[1].size()-1];i<=m;i++)update(1,1,m,i);for(int i=1;i<=n;i++){for(int j=0;j<w[i].size();j++)update(1,1,m,w[i][j]);if(flag)ans+=query(1,1,m,1,m);else if(w[i].size()){ans+=query(1,1,m,w[i][w[i].size()-1],m);if(w[i][w[i].size()-1]==1)flag=1;}}printf("%lld\n",n*m-ans);return 0;
}