离谱题,结论出奇的简单。
首先我们考虑\(O(nq)\)怎么做。
显然所有C
都要放在最终序列中,然后问题就变成往里面填T
。
我们考虑第一个T
填在能填的最开始的位置上,因为如果这个T
往后移动,那么其实只会更劣。因此一个基础的想法就是能填就填。
我们发现这个形式和最大子段和满足的性质是一样的,即一个最大子段和是满足这个性质的。
而对应的,一个区间的最大子段和去掉以后,前区间的后缀和后区间的前缀都是非正的。
而考虑现在将这两个区间删掉若干个T
使得这两个区间的总和恰好为\(0\),容易发现这是必要的,为了最优,我们应该使左区间删掉右边的,右区间删掉左边的。这样左区间的前缀和右区间的后缀本身就是非负的,而左区间的后缀和右区间的前缀也被删成了非负的。
所以答案就是最大子段和减去区间和,用线段树维护,时间复杂度\(O(n+q\log n)\)。
code:
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=600+5,M=2e7,K=(1<<10)+5,mod=1e9+7,Mod=mod-1;ll INF=1e18+7;const db eps=1e-5;mt19937 rnd(time(0));
int n,m,k,x,y,Q[N],P[N];ll f[N][N],g[N],Ans;
int main(){
freopen("1.in","r",stdin);
int i,j,h;scanf("%d%d",&n,&k);m=2*n;for(i=1;i<=k;i++) scanf("%d%d",&x,&y),P[x]=y,P[y]=x,Q[x]=Q[y]=1;
for(i=1;i<=m;i++) Q[i]=Q[i-1]+(!Q[i]);for(g[0]=1,i=2;i<=m;i+=2) g[i]=g[i-2]*(i-1)%mod;
for(i=m;i;i--){
for(j=i;j<=m;j++) {
int Fl=0;if((Q[j]-Q[i-1])&1) continue;for(h=i;h<=j;h++) if(Q[h]==Q[h-1]&&(P[h]<i||P[h]>j)) {Fl=1;break;}if(Fl) continue;
f[i][j]=g[Q[j]-Q[i-1]];for(h=i+1;h<=j;h++) f[i][j]=(f[i][j]+(mod-g[Q[h-1]-Q[i-1]])*f[h][j])%mod;Ans+=f[i][j]*g[m-2*k-(Q[j]-Q[i-1])]%mod;
}
}printf("%lld\n",Ans%mod);
}
标签:子段,P4786,luogu,删掉,BalkanOI2018,long,区间,using,define
From: https://www.cnblogs.com/275307894a/p/16886427.html