C20220725T4 基因进化

给出序列 \(s\) ，可以进行翻转操作，使 \(s_{1,i}\) 翻转，但 \(i\) 只能递增，且有 \(m\) 个位置不能翻转。 \(m\leq n\leq 3\times 10^5\) ，多组数据， \(T\leq100\) 。

对于前 \(i\) 个数，所能产生的最小的字典序是多少；无论后面的怎么翻，之前的一定是越小越好；对于相邻两
个能翻的位置 \(i,j \,\,(i<j)\) 。前 \(j\) 个的最小值要么是前 \(i\) 个的最小值接上 \(i\) 到 \(j\) 这一段；要么是 \(i\) 到 \(j\) 的翻转接上前 \(i\) 个的最小值（同时在 \(i\) 和 \(j\) 翻转）； 每次翻转前判断哪种方式更优。

用哈希+二分的方式判断优劣程度直接用两个队列，记录头插入和尾插入的数； 维护队列的前缀哈希值和后缀哈希值；用这些一定可以拼出一段的哈希值。

#include<bits/stdc++.h>
using namespace std;
#define MAXN (int)(3e5+5)
#define MAXM (int)(6e5+9)
#define Mod 998244353
#define P (int)(1e9+7)
#define Q (int)(1e9+9)
#define GP 10001
#define GQ 10007
#define ll long long
#define ull unsigned long long
#define chkmax(x,y) x=max(x,y)
#define chkmin(x,y) x=min(x,y)
struct IO{
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> inline IO & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
    inline void push(const char &c) {
    	putchar(c);
	}
	template <class T>
	inline void write(T x){
		if (x < 0) x = -x, push('-');
		static T sta[35];
		T top = 0;
		do {
			sta[top++] = x % 10, x /= 10;
		} while (x);
		while (top) push(sta[--top] + '0');
	}
	template <class T>
	inline void write(T x, char lastChar){
		write(x),push(lastChar);
	}
}io;

struct info{
	int x,y;
};

int mul(int a,int b,int p){
	int ret=1;
	while(b){
		if(b&1)
			ret=ret*b%p;
		b>>=1;
		a=a*a%p;
	}
	return ret;
}
info operator +(info a,info b){
	info ans;
	ans.x=(a.x+b.x>=P)?(a.x+b.x-P):(a.x+b.x);
	ans.y=(a.y+b.y>=Q)?(a.y+b.y-Q):(a.y+b.y);
	return ans;
}
info operator -(info a,info b){
	info ans;
	ans.x=(a.x-b.x>=0)?(a.x-b.x):(a.x-b.x+P);
	ans.y=(a.y-b.y>=0)?(a.y-b.y):(a.y-b.y+Q);
	return ans;
}
info operator *(info a,int b){
	info ans;
	ans.x=1ll*a.x*b%P;
	ans.y=1ll*a.y*b%Q;
	return ans;
}
info operator *(info a,info b){
	info ans;
	ans.x=1ll*a.x*b.x%P;
	ans.y=1ll*a.y*b.y%Q;
	return ans;
}
bool operator ==(info a,info b){
	return a.x==b.x && a.y==b.y;
}

info base,powb[MAXM];
info invb,powi[MAXM],sum[MAXM];
void updata(int &x,int y){
	x+=y;
	if(x>=Mod)
		x-=Mod;
}
bool mark[MAXN];
int n,m,l,r,ans[MAXM];
int a[MAXN],powk[MAXN];
void pushback(int x){
	ans[++r]=x;
	sum[r]=sum[r-1]+powb[r]*x;
}
void pushfront(int x){
	ans[--l]=x;
	sum[l-1]=sum[l]-powb[l]*x;
}
bool cmp(int s,int t,int len){
	int l=0,r=len;
	while(l<r){
		int mid=(l+r+1)>>1;
		if((sum[s+mid-1]-sum[s-1])==(sum[t+mid-1]-sum[t-1])*(powb[s-t]))
			l=mid;
		else
			r=mid-1;
	}
	if(l==len || ans[s+l]<ans[t+l])
		return 1;
	else
		return 0;
}
int main(){
	powb[0]=powi[0]=(info){1,1};
	base=(info){GP,GQ};
	invb=(info){mul(GP,P-2,P),mul(GQ,Q-2,Q)};
	for(int i=1;i<MAXM;++i){
		powb[i]=powb[i-1]*base;
		powi[i]=powi[i-1]*invb;
	}
	powk[0]=1;
	for(int i=1;i<MAXN;++i){
		powk[i]=37ll*powk[i-1]%Mod;
	}
	int T;
	io>>T;
	while(T--){
		io>>n>>m;
		for(int i=1;i<=n;++i){
			io>>a[i];
			mark[i]=0;
		}
		for(int i=1;i<=m;++i){
			int x;
			io>>x;
			mark[x]=1;
		}
		ans[l=r=MAXN]=a[1];
		sum[l-1]=(info){0,0};
		sum[l]=powb[l]*a[1];
		int last=1;
		for(int i=2;i<=n;++i){
			if(mark[i]==0){
				int len=i-last;
				int x=l,length=r-l+1;
				for(int j=last+1;j<=i;++j){
					pushback(a[j]);
					pushfront(a[j]);
				}
				int y=l;
				if(cmp(x,y,length+len)){
					while(len--)
						l++;
				}
				else{
					while(len--)
						r--;
				}
				last=i;
			}
		}
		while(last!=n)
			pushback(a[++last]);
		int final=0;
		for(int i=l;i<=r;++i){
			updata(final,1ll*powk[i-l]*ans[i]%Mod);
		}
		io.write(final,'\n');
	}
}