和FallDream dalao一起从学长那借了个小号打Div2，他切ABE我做CD，我这里就写下CD题解，剩下的戳这里
AC:All Rank:33 小号Rating:1539+217->1756
C.Alyona and Spreadsheet
题目大意：给出一个n*m的数字矩阵a，k次询问，每次给li,ri，求是否有一列的a[li][j],a[li+1][j],...a[ri][j]组成一个不下降序列。（n*m<=100,000，k<=100,000）
思路：O(n*m)扫一遍可以预处理出每个ri最小的li，我菜，写了线段树。
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
inline int read()
{
int x=;char c;
while((c=getchar())<''||c>'');
for(;c>=''&&c<='';c=getchar())x=(x<<)+(x<<)+c-'';
return x;
}
#define MN 100000
#define N 131072
#define INF 0x7FFFFFFF
vector<int> v[MN+];
vector<pair<int,int> > q[MN+];
int t[N*+],ans[MN+];
void change(int k,int x){for(t[k+=N]=x;k>>=;)t[k]=min(t[k<<],t[(k<<)+]);}
int main()
{
int n,m,k,i,j;
n=read();m=read();
for(i=;i<=m;++i)v[].push_back(INF);
for(i=;i<=n;++i)v[i].push_back();
for(i=;i<=n;++i)for(j=;j<=m;++j)v[i].push_back(read());
for(k=read(),i=;i<k;++i)j=read(),q[read()].push_back(make_pair(j,i));
memset(t,,sizeof(t));
for(i=;i<=n;++i)
{
for(j=;j<=m;++j)if(v[i][j]<v[i-][j])change(j,i);
for(j=;j<q[i].size();++j)ans[q[i][j].second]=(t[]<=q[i][j].first);
}
for(i=;i<k;++i)puts(ans[i]?"Yes":"No");
}
D.
题目大意：给N个字符串，从中删掉最少的字符使得字符串按字典序排序。（字符数量<=500,000）
思路：我写了个分治……solve(l,r,p)表示第l个到第r个前p-1个都一样，从后往前找到第一个s[i][p]>s[i+1][p]，把第l个到第i个p以后都截掉，然后按第p个字符分成几块继续分治。其实只要从最后一个往前贪心删掉就可以了。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define MN 500000
#define INF 0x7FFFFFFF
string s[MN+];
int L[MN+];
int C(int x,int y){return y<=L[x]?s[x][y]:;}
void solve(int l,int r,int p)
{
int i,j,mn=INF;
for(i=r;i>=l;--i)
{
if(C(i,p)>mn)L[i]=p-;
mn=min(mn,C(i,p));
}
for(i=l;i<=r;i=j)
{
for(j=i;j<=r&&C(i,p)==C(j,p);++j);
if(C(i,p))solve(i,j-,p+);
}
}
int main()
{
int n,i,j;
cin>>n;
for(i=;i<=n;++i)
{
cin>>s[i];
L[i]=s[i].size()-;
}
solve(,n,);
for(i=;i<=n;++i,puts(""))for(j=;j<=L[i];++j)putchar(s[i][j]);
}