施工中

ds快乐场，结果一题不会呜呜呜

D. Display Substring

毫无思路，被 D 了 QAQ

二分答案 (ans)，对每个 SAM 上的结点二分价值 (le ans) 的最大长度。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int lst,cnt,len[N],pre[N],ch[N][26],pos[N],n,c[26],sum[N];
long long k; char s[N];
void extend(int c)
{
	int p=lst,np=++cnt;lst=np;
	len[np]=len[p]+1; pos[np]=len[np];
	for(;p&&!ch[p][c];p=pre[p]) ch[p][c]=np;
	if(!p)
	{
		pre[np]=1;
		return ;
	}
	int q=ch[p][c];
	if(len[p]+1==len[q])
	{
		pre[np]=q;
		return ;
	}
	int nq=++cnt;len[nq]=len[p]+1; pos[nq]=pos[q];
	memcpy(ch[nq],ch[q],sizeof(ch[q]));
	pre[nq]=pre[q],pre[q]=pre[np]=nq;
	for(;ch[p][c]==q;p=pre[p])ch[p][c]=nq;
}
bool check(int x)
{
	long long res=0;
	for(int i=2;i<=cnt;++i)
	{
		int l=len[pre[i]]+1,r=len[i],al=-1;
		while(l<=r)
		{
			int mid=l+r>>1;
			if(sum[pos[i]]-sum[pos[i]-mid]<=x) al=mid,l=mid+1;
			else r=mid-1;
		}
		if(al!=-1) res+=al-len[pre[i]];
	}
	return res>=k;
}
void init()
{
	for(int i=1;i<=cnt;++i) 
	{
		len[i]=pre[i]=pos[i]=0;
		memset(ch[i],0,sizeof(ch[i]));
	}
	lst=cnt=1;
}
int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		init();
		scanf("%d%lld%s",&n,&k,s+1);
		for(int i=0;i<26;++i) scanf("%d",&c[i]);
		for(int i=1;i<=n;++i)
		{
			sum[i]=sum[i-1]+c[s[i]-'a'];
			extend(s[i]-'a');
		}
		int l=1,r=sum[n];
		while(l<=r)
		{
			int mid=l+r>>1;
			check(mid)?r=mid-1:l=mid+1;
		}
		printf("%d
",r==sum[n]?-1:r+1);
	}
}

E. Didn’t I Say to Make My Abilities Average in the Next Life?!

在写了在写了。

G. Increasing Subsequence

在写了在写了。

H. Lawn of the Dead

这题并不难。我们只用对于每一列的每两个相邻的障碍，找到上一列能到达的最低点，从这点一直到上面的障碍的点一定可达。使用线段树维护可达点即可。

#include<bits/stdc++.h>
using namespace std;
namespace io {
	const int SIZE=(1<<21)+1;
	char ibuf[SIZE],*iS,*iT,c; int x;
	#define gc()(iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline int gi (){
		for(c=gc();c<'0'||c>'9';c=gc());
		for(x=0;c<='9'&&c>='0';c=gc()) x=(x<<1)+(x<<3)+(c&15); return x;
	}
} using io::gi;
const int N=1e5+5;
bool st[N<<2];
int n,m,k,tg[N<<2];
vector<int> v[N];
#define lx (x<<1)
#define rx (x<<1|1)
void pushdown(int x)
{
	if(tg[x]==-1) return ;
	st[lx]=st[rx]=tg[lx]=tg[rx]=tg[x];
	tg[x]=-1;
}
void update(int x, int l, int r, int sl, int sr, int w)
{
	if(sl>sr) return ;
	if(sl<=l&&r<=sr)
	{
		st[x]=tg[x]=w;
		return ;
	}
	pushdown(x);
	int mid=l+r>>1;
	if(sl<=mid) update(lx,l,mid,sl,sr,w);
	if(sr>mid) update(rx,mid+1,r,sl,sr,w);
	st[x]=st[lx]|st[rx];
}
int query(int x, int l, int r, int s)
{
	if(s>m||!st[x]) return m+1;
	if(l==r) return l;
	pushdown(x);
	int mid=l+r>>1;
	if(s<=l) return st[lx]?query(lx,l,mid,s):query(rx,mid+1,r,s);
	int ans=m+1;
	if(s<=mid) return min(query(lx,l,mid,s),query(rx,mid+1,r,s));
	return query(rx,mid+1,r,s);
}
void init()
{
	for(int i=1;i<=n;++i) v[i].clear();
	for(int i=1;i<=(m<<2);++i) st[i]=0,tg[i]=-1;
}
int main()
{
	int T=gi();
	while(T--)
	{
		init();
		n=gi(),m=gi(),k=gi();
		for(int i=1;i<=k;++i)
		{
			int x=gi(),y=gi();
			v[x].push_back(y);
		}
		for(int i=1;i<=n;++i)
		{
			v[i].push_back(0),v[i].push_back(m+1);
			sort(v[i].begin(),v[i].end());
		}
		long long ans=0;
		update(1,1,m,1,v[1][1]-1,1);
		ans+=v[1][1]-1;
		for(int i=2;i<=n;++i)
		{
			for(int j=0;j<v[i].size()-1;++j)
			{
				int x=min(v[i][j+1],query(1,1,m,v[i][j]+1));
				update(1,1,m,max(1,v[i][j]),x-1,0);
				update(1,1,m,x,v[i][j+1]-1,1);
				ans+=max(0,v[i][j+1]-x);
			}
		}
		printf("%lld
",ans);
	}
}