DZY 's BLOG

题意：给定一个序列，每次询问左端点在[a,b]中，右端点在[c,d]中的子序列中，最大的中位数。强制在线。

前几天做到与这道题有一点点类似的。那道题是给定一个序列，求多少个子序列的中位数大于等于给定值M。

这两道题中的中位数的定义都是一样的。设序列S从大到小排序后为S[1..k]，中位数为M=S[k/2向上取整]。

那就意味着，在序列S中，大于等于M的数大于等于k/2。如果把序列S转化为T，T[i]=1(S[i]>=M),-1(S[i]<M)，则ΣT[i]一定非负。

同理，如果对于任意一个M。将序列S转化为T之后，如果ΣT[i]非负。那么这个序列的中位数一定大于等于M。

回到这道题。我们可以先考虑一个弱版：只询问一次。

有了上面那道题的经验。对于M<M'，如果发现中位数大于等于M'，那一定也大于等于M。所以有单调性，很容易就想到了二分。二分M。得到T[]。因为要求了左端点和右端点。所以，如果能在满足要求的情况下找到这一段ΣT[i..j]（i∈[a,b]，j∈[c,d]）非负，那么中位数一定就大于等于M了。所以，我们只需要求出符合要求的最大子序列和，看是不是非负即可。

感觉回到了GSS。线段树维护lmax,rmax,sum即可。因为有a<b<c<d，所以[a,b],[c,d]是互不包含的。最大连续子序列和就是[a,b]的rmax+(b,c)的sum+[c,d]的lmax。

另外n个数都是要离散化的这是必然的。二分的时候二分下标。

现在感觉已经很明了了。这样的话。二分logn。重建序列T和线段树nlogn。总复杂度是O(nlog^2n)。可以很好的解决一次询问。= =

多个询问怎么办。O(nqlog^2n)作死？其实瓶颈在这：为什么每次都要重建线段树？根本就不需要。

假设离散化的时候数值是从小到大排序的。那我们可以这么想，二分到M时，排序后的下标第1~M-1位上都是-1。第M~n位上都是1。然后还是跟上面一样的方法判定。

这就要用到函数式编程的思想。在原来的基础上不做修改，继续建树，也就是函数式线段树。

具体来说：初始的树，每个位置都是1。序列从小到大插入主席树时，修改第i棵树的时候，第i-1大的数的位置上改为-1。这样以此类推，就有n棵不同版本的线段树。

二分到M时，就在第M棵线段树上查询。可以保证此时下标为1~M-1的位置上的数都是-1。其余位置上都是1。这样就可以进行查询了。

这样就没问题了。二分logn。建函数式线段树nlogn。查询一次logn。总复杂度(nlogn+qlog^2n)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
	int sum,lmax,rmax;
	node(){};
	node(int s,int l,int r):sum(s),lmax(l),rmax(r){}; 
}seg[5000000],z;
int lc[5000000],rc[5000000],T[30000],q[4],ans=0,tot=0,n,Q;
pair<int,int>a[30000];
char buf[4000000],*pt=buf,*o=buf;
inline int getint(){
    int s=0; while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s;
}
inline void print(int x){
    char str[12],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}*o++='\n';
}
inline node operator + (const node &a,const node &b){
	return node(a.sum+b.sum,max(a.lmax,a.sum+b.lmax),max(b.rmax,b.sum+a.rmax));
}void build(int l,int r,int &rt){
	rt=++tot;
	if(l==r){	seg[rt]=node(1,1,1);	return;}
	int m=l+r>>1;
	build(l,m,lc[rt]);	build(m+1,r,rc[rt]);
	seg[rt]=seg[lc[rt]]+seg[rc[rt]];
}void modify(int p,int k,int v,int l,int r,int &rt){
	rt=++tot;
	lc[rt]=lc[p];	rc[rt]=rc[p];
	if(l==r){	seg[rt]=node(v,v,v);	return;}
	int m=l+r>>1;
	if(k<=m)	modify(lc[p],k,v,l,m,lc[rt]);
	else		modify(rc[p],k,v,m+1,r,rc[rt]);
	seg[rt]=seg[lc[rt]]+seg[rc[rt]];
}node ask(int L,int R,int l,int r,int rt){
	if(L>R)	return node(0,0,0); 
	if(L==l&&r==R)	return seg[rt];
	int m=l+r>>1;
	if(R<=m)	return ask(L,R,l,m,lc[rt]);
	else if(L>m)	return ask(L,R,m+1,r,rc[rt]);
	else	return ask(L,m,l,m,lc[rt])+ask(m+1,R,m+1,r,rc[rt]);
}inline int check(int k){
	return ask(q[0],q[1],0,n-1,T[k]).rmax+ask(q[1]+1,q[2]-1,0,n-1,T[k]).sum+ask(q[2],q[3],0,n-1,T[k]).lmax>=0;
}int main(){
	fread(buf,1,4000000,stdin);	n=getint();
	for(int i=0;i<n;i++)	a[a[i].second=i].first=getint();
	sort(a,a+n);			build(0,n-1,T[0]);
	for(int i=1;i<n;i++)	modify(T[i-1],a[i-1].second,-1,0,n-1,T[i]);
	Q=getint();
	while(Q--){
		q[0]=(getint()+ans)%n;	q[1]=(getint()+ans)%n;	q[2]=(getint()+ans)%n;	q[3]=(getint()+ans)%n;
		sort(q,q+4);
		int l=0,r=n-1,mid;
		while(l<=r)	if(check(mid=l+r>>1))	l=mid+1;	else	r=mid-1;
		print(ans=a[l-1].first);
	}return fwrite(buf,1,o-buf,stdout),0;
}

二分+后缀自动机还是比较好想的。dp优化只能膜拜题解了。==

题意：给定一些01字符串作为标准作文库。然后给你几篇作文。对于每篇作文，把这篇作文分成若干段后，如果一段的长度不小于L，且是标准作文库中某个字符串的连续子串，这样这一段作文就是匹配的。求L的最大值，使得这篇作文的90%是匹配的。

一眼看出是二分+判定。因为如果L0可行，那小于L0的L都可行。

然后就可以考虑如何判定。分段的话应该是要dp了。设这个作文是S。

先预处理出一个数组d[i],d[i]=max{i-j+1|S[j..i]是标准作文库中某个字符串的连续子串}

这个用后缀自动机。把标准作文库里的所有字符串拼起来。中间加一个分隔符2好了。然后O(n)建后缀自动机。

然后让S在自动机上跑。

跑的过程具体就是：从root开始，如果下一个字符可以转移就转移，更新len值，如果不能就一直回退直到可以转移，回到根了那len=0，如果还没到根，len=当前结点的l值，并且继续转移。

定义数组f[i]为S[1..i]匹配的最大长度。则f[i]=max{f[j]+i-j|i-d[i]<=j<=i-L}。可惜这样dp是O(n^2)的承受不起。

优化：

f[i]=i+max{f[j]-j|i-d[i]<=j<=i-L}。然后令g[j]=f[j]-j。

考虑它的决策区间。

首先i-d[i]是非严格递增的。

如果有某个i，使得i-d[i]>i+1-d[i+1]，由d[i]的意义知S[i-d[i]+1..i]和S[i+1-d[i+1]+1..i+1]是字典中某个串的子串。
由于i-d[i]+1>i+1-d[i+1]+1，知S[i+1-d[i+1]+1..i]也是字典中某个串的子串且比S[i-d[i]+1..i]更长，这与d[i]的定义中的max违背。

i-L是严格递增的。显然。

那么[i-d[i],i-L]只会右移。那么用g[]递减的一个单调队列维护决策区间即可。

最后的复杂度应该是O(nlogn)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1100010;
int l[maxn],ch[maxn][3],d[maxn],f[maxn],g[maxn],q[maxn],fa[maxn];
int rt=1,tail=1,tot=1,n,len;    char s[maxn];
void add(int c){
    int p=tail,np=++tot,r,q;
    l[np]=l[p]+1;   tail=np;
    for(;p&&!ch[p][c];p=fa[p])  ch[p][c]=np;
    if(!p){ fa[np]=rt;  return;}
    if(l[p]+1==l[q=ch[p][c]]){  fa[np]=q;   return;}
    fa[r=++tot]=fa[q];  memcpy(ch[r],ch[q],sizeof(ch[r]));
    l[r]=l[p]+1;    fa[np]=fa[q]=r;
    for(;p&&ch[p][c]==q;p=fa[p])    ch[p][c]=r;
}void init(){
    int p=rt,k=0,x;
    for(int i=1;i<=n;i++){
        if(ch[p][x=s[i]-48])    k++,    p=ch[p][x]; else{
            while(p&&!ch[p][x]) p=fa[p];
            if(!p)  p=rt,k=0;   else    k=l[p]+1,p=ch[p][x];
        }d[i]=k;
    }
}int mt(int r){
    int s=1,e=0,t;
    for(int i=1;i<=n;i++){
        if((t=i-r)>=0){
            while(s<=e&&g[q[e]]<g[t])   e--;
            q[++e]=t;
        }while(s<=e&&q[s]<i-d[i])    s++;
        f[i]=f[i-1];
        if(s<=e&&f[i]<g[q[s]]+i)    f[i]=g[q[s]]+i;
        g[i]=f[i]-i;
    }return f[n]>=len;
}int main(){
    int tc,m;   scanf("%d%d",&tc,&m);
    for(int i=1;i<=m;i++){
        scanf("%s",s+1);
        int k=strlen(s+1);
        for(int j=1;j<=k;j++)    add(s[j]-48);
        if(i!=m)add(2);
    }while(tc--){
        scanf("%s",s+1);    n=strlen(s+1);
        len=(int)(ceil((double)n*0.9));
        init(); if(!mt(1)){   printf("0\n");  continue;}
        int L=2,R=n,mid;
        while(L<=R){
            mid=(L+R)>>1;
            if(mt(mid)) L=mid+1;    else    R=mid-1;
        }printf("%d\n",R);
    }return 0;
} 

煞笔的煞笔又来发水题题解了！

二分答案。先判一级公路然后判二级公路。没了。

1A什么的不必多说。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct E{ int u,v,c1,c2;}e[20005];
inline bool C(E a,E b){ return a.c1<b.c1;}
int F[10005],n,k,m; char buf[2000000],*pt=buf;
int GF(int x){  return x==F[x]?x:F[x]=GF(F[x]);}
inline int getint(){ 
    int r=0;while(*pt<'0'||*pt>'9')pt++;while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline int ok(int lmt){
    int ck=0,ca=0;
    for(int i=1;i<=n;i++) F[i]=i;
    for(int i=1;i<=m;i++){
        if(e[i].c1<=lmt){
            int u=GF(e[i].u),v=GF(e[i].v);
            if(u!=v) F[u]=v,ck++,ca++;
            if(ca==n-1) return 1;
        }else{
            if(ck<k) return 0;
            if(min(e[i].c1,e[i].c2)>lmt) continue;
            int u=GF(e[i].u),v=GF(e[i].v);
            if(u!=v) F[u]=v,ca++;
            if(ca==n-1) return 1;
        }
    }return 0;
}int main(){
    fread(pt,1,2000000,stdin);  int i;
    for(n=getint(),k=getint(),m=getint(),i=1;i<m;i++)
        e[i].u=getint(),e[i].v=getint(),e[i].c1=getint(),e[i].c2=getint();
    sort(e+1,e+m+1,C);  int l=0,r=1000000009,mid;
    while(l<=r){
        mid=l+r>>1;
        if(ok(mid)) r=mid-1;    else    l=mid+1;
    }printf("%d\n",l);return 0;
}