Darkmoon Faire
题目:
Darkmoon Faire
题意：
n个数，分成若干段，使得每段最大值在奇数位上，最小值在偶数位上。
问分割方案数。
题解:
每段max,min让人想到区间异或和异或区间最大值异或区间最小值这题。
利用分治，来完成方程转移。
跨越中线的情况分4种：
1.max,min都在左边
2.max,min都在右边
3.max在左,min在右
4.max在右,min在左
具体实现需要用到大量前缀和和差分来优化，实现较复杂。
代码:
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define last Lst
#define gc getchar
#define int long long
const int N=1e6+5;
const int mod=998244353;
int n,m,a[N],S1[N],S2[N],S3[N],S4[N],ma[N],mi[N],A[N],f[N],ji[N],ou[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
int ret=0,f=0;char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){ret=ret*10+c-48;c=gc();}
if(f)return -ret;return ret;
}
void solve(int l,int r)
{
if(l==r)return;
int mid=(l+r)/2;
solve(l,mid);
S1[l-1]=S2[l-1]=0;
if((l-1)%2==1)S1[l-1]=f[l-1];
else S2[l-1]=f[l-1];
for(int i=l;i<=mid;i++)
{
S1[i]=S1[i-1];
S2[i]=S2[i-1];
if(i%2==1)S1[i]=(S1[i]+f[i])%mod;
else S2[i]=(S2[i]+f[i])%mod;
}
for(int i=l;i<=r;i++)A[i]=ji[i]=ou[i]=0;
int maxl,maxr,minl,minr,pin1,pin2;
maxl=minl=mid;
for(int i=mid;i>=l;i--)
{
if(a[i]>a[maxl])maxl=i;
if(a[i]<a[minl])minl=i;
ma[i]=maxl;
mi[i]=minl;
}
maxr=minr=mid+1;
for(int i=mid+1;i<=r;i++)
{
if(a[i]>a[maxr])maxr=i;
if(a[i]<a[minr])minr=i;
ma[i]=maxr;
mi[i]=minr;
}
S3[l-1]=S4[l-1]=0;
if((l-1)%2==1&&mi[l]%2==1)S3[l-1]=f[l-1];
if((l-1)%2==0&&mi[l]%2==0)S4[l-1]=f[l-1];
for(int i=l;i<mid;i++)
{
S3[i]=S3[i-1];
S4[i]=S4[i-1];
if(i%2==1&&mi[i+1]%2==1)S3[i]=(S3[i]+f[i])%mod;
if(i%2==0&&mi[i+1]%2==0)S4[i]=(S4[i]+f[i])%mod;
}
//1.max left min left
pin1=mid+1;
for(int i=mid;i>=l;i--)
{
while(pin1<=r&&a[mi[pin1]]>a[mi[i]]&&a[ma[pin1]]<a[ma[i]])pin1++;
//mid+1~pin1-1
if((ma[i]-i+1)%2==1&&(mi[i]-i+1)%2==0)
{
A[mid+1]=(A[mid+1]+f[i-1])%mod;
A[pin1]=(A[pin1]-f[i-1]+mod)%mod;
}
}
//2.max right min right
pin1=mid;
for(int i=mid+1;i<=r;i++)
{
while(pin1>=l&&a[mi[pin1]]>a[mi[i]]&&a[ma[pin1]]<a[ma[i]])pin1--;
//pin1+1~mid
if(ma[i]%2==mi[i]%2)continue;
if(ma[i]%2==0)
{
if(pin1==l-1)f[i]=(f[i]+S1[mid-1])%mod;
else f[i]=(f[i]+S1[mid-1]-S1[pin1-1]+mod)%mod;
}
else{
if(pin1==l-1)f[i]=(f[i]+S2[mid-1])%mod;
else f[i]=(f[i]+S2[mid-1]-S2[pin1-1]+mod)%mod;
}
// for(int j=pin1;j<=mid-1;j++)
// if(ma[i]%2!=j%2)
// {
// if(ma[i]%2==0)f[i]=(f[i]+S1[j]-S1[j-1]+mod)%mod;
// else f[i]=(f[i]+S2[j]-S2[j-1]+mod)%mod;
// }
}
//3.max left min right
pin1=pin2=mid+1;
for(int i=mid;i>=l;i--)
{
while(pin1<=r&&a[mi[i]]<a[mi[pin1]])pin1++;
while(pin2<=r&&a[ma[i]]>a[ma[pin2]])pin2++;
if(pin1<pin2)
{
//pin1~pin2-1
if((ma[i]-i+1)%2==0)continue;
if(i%2==0)
{
ji[pin1]=(ji[pin1]+f[i-1])%mod;
ji[pin2]=(ji[pin2]-f[i-1]+mod)%mod;
}
else{
ou[pin1]=(ou[pin1]+f[i-1])%mod;
ou[pin2]=(ou[pin2]-f[i-1]+mod)%mod;
}
// for(int j=pin1;j<=pin2-1;j++)
// if(mi[j]%2!=i%2)
// f[j]=(f[j]+f[i-1])%mod;
}
}
//4.max right min left
pin1=pin2=mid;
for(int i=mid+1;i<=r;i++)
{
while(pin1>=l&&a[mi[i]]<a[mi[pin1]])pin1--;
while(pin2>=l&&a[ma[i]]>a[ma[pin2]])pin2--;
if(pin1>pin2)
{
//pin2+1~pin1
if(ma[i]%2==0)//mi[j+1]%2==1 j%2==1
{
if(pin2==l-1)f[i]=(f[i]+S3[pin1-1])%mod;
else f[i]=(f[i]+S3[pin1-1]-S3[pin2-1]+mod)%mod;
}
else{//mi[j+1]%2==0 j%2==1
if(pin2==l-1)f[i]=(f[i]+S4[pin1-1])%mod;
else f[i]=(f[i]+S4[pin1-1]-S4[pin2-1]+mod)%mod;
}
// for(int j=pin2;j<=pin1-1;j++)
// if((ma[i]-j)%2==1&&(mi[j+1]-j)%2==0)
// f[i]=(f[i]+f[j])%mod;
}
}
for(int i=l+1;i<=r;i++)A[i]=(A[i]+A[i-1])%mod;
for(int i=mid+1;i<=r;i++)f[i]=(f[i]+A[i])%mod;
for(int i=l+1;i<=r;i++)ji[i]=(ji[i]+ji[i-1])%mod;
for(int i=mid+1;i<=r;i++)
if(mi[i]%2==1)f[i]=(f[i]+ji[i])%mod;
for(int i=l+1;i<=r;i++)ou[i]=(ou[i]+ou[i-1])%mod;
for(int i=mid+1;i<=r;i++)
if(mi[i]%2==0)f[i]=(f[i]+ou[i])%mod;
solve(mid+1,r);
}
signed main()
{
int T=read();
while(T--)
{
n=read();
for(int i=1;i<=n;i++)f[i]=0;
for(int i=1;i<=n;i++)a[i]=read();
f[0]=1;
solve(1,n);
// for(int i=1;i<=n;i++)cout<<f[i]<<" ";
cout<<f[n]<<endl;
}
return 0;
}
/*
3
15
9 1 2 11 7 15 6 8 10 5 4 12 3 14 13
5
3 2 4 1 8
10
9 1 2 4 7 3 6 8 10 5
*/
