cf1591f Non-equal Neighbours / arc115e LEQ and NEQ
给出一个长度为 \(n\) 的序列，为 \(a_1,a_2,\cdots,a_n\) . 求出符合以下条件的序列 \(b_1,b_2,\cdots,b_n\) ，模 \(998244353\) .
- \(1\leq b_i\leq a_i,1\leq i\leq n\)
- \(b_i\not=b_{i+1},1\leq i\leq n-1\)
\(1\leq n\leq 2\cdot 10^5,1\leq a_i\leq 10^9\)
sol1
考虑把 \(a_i\leq 10^9\) 修改成 \(\leq n\) .
用 \(dp(i,j)\) 表示第 \(i\) 项为 \(j\) 的方案数量 .
\(dp(i+1,k)=\sum dp(i,j)-dp(i,k)\)
考虑是否可以线段树维护，这个 $\sum $ 很简单，直接区间加就可以，但是这个 \(-dp(i,k)\) 发现有点难办，接下来有两种方法 .
- 我的方法是对于 $\sum $ 取反，加上去，这样就会得到 \(-dp(i+1,k)\) ，记录一下正负情况即可 .
- lxr提出这个可以直接 \(\times (-1)\) .
当然是我的方法好写，只需要一个tag . 但是这还有一个问题，需要区间赋值，当 \(a_{i-1}> a_i\) 的时候 , \(dp(i,a_{i-1}+1)\) 到 \(dp(i,a_i)\) 都要赋值成 \(0\) .
发现，可以把 \(a_i\) 离散化，中间每一段在任意时刻的值都是相同的 .
时间复杂度 : \(O(n\log n)\)
空间复杂度 : \(O(n)\)
code
#include
using namespace std;
const int N=5e5+10;
const int mod=998244353;
int n;
int a[N];
mapmp;
int pos[N],cnt=0;
class node{public:int val,sz,tg1,tg2;}ts[N<<2];
void build(int x,int l,int r){
if(l==r){
ts[x].sz=(pos[l]-(l?pos[l-1]:0))%mod;
ts[x].tg1=ts[x].tg2=0;
ts[x].val=0;
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
ts[x].sz=(ts[x<<1].sz+ts[x<<1|1].sz)%mod;
ts[x].tg1=ts[x].tg2=0;
ts[x].val=0;
}
void pd(int x){
if(!ts[x].tg1&&!ts[x].tg2)return;
if(ts[x].tg1){
ts[x<<1].val=ts[x<<1|1].val=0;
ts[x<<1].tg1=ts[x<<1|1].tg1=1;
ts[x<<1].tg2=ts[x<<1|1].tg2=0;
}
if(ts[x].tg2){
ts[x<<1].val=(ts[x<<1].val+1ll*ts[x<<1].sz*ts[x].tg2%mod)%mod;
ts[x<<1|1].val=(ts[x<<1|1].val+1ll*ts[x<<1|1].sz*ts[x].tg2%mod)%mod;
ts[x<<1].tg2=(ts[x<<1].tg2+ts[x].tg2)%mod;
ts[x<<1|1].tg2=(ts[x<<1|1].tg2+ts[x].tg2)%mod;
}
ts[x].tg1=ts[x].tg2=0;
}
void mdy(int x,int l,int r,int cl,int cr){
if(l==cl&&r==cr){
if(l!=r)pd(x);
ts[x].tg1=1;
ts[x].tg2=0;
ts[x].val=0;
return;
}
pd(x);
int mid=(l+r)>>1;
if(cr<=mid)mdy(x<<1,l,mid,cl,cr);
else if(mid+1<=cl)mdy(x<<1|1,mid+1,r,cl,cr);
else mdy(x<<1,l,mid,cl,mid),mdy(x<<1|1,mid+1,r,mid+1,cr);
ts[x].val=(ts[x<<1].val+ts[x<<1|1].val)%mod;
}
void upd(int x,int l,int r,int cl,int cr,int val){
if(l==cl&&r==cr){
if(l!=r)pd(x);
ts[x].tg2=(ts[x].tg2+val)%mod;
ts[x].val=(ts[x].val+1ll*val*ts[x].sz%mod)%mod;
return;
}
pd(x);
int mid=(l+r)>>1;
if(cr<=mid)upd(x<<1,l,mid,cl,cr,val);
else if(mid+1<=cl)upd(x<<1|1,mid+1,r,cl,cr,val);
else upd(x<<1,l,mid,cl,mid,val),upd(x<<1|1,mid+1,r,mid+1,cr,val);
ts[x].val=(ts[x<<1].val+ts[x<<1|1].val)%mod;
}
int qry(int x,int l,int r,int pos){
if(l==r)return ts[x].val;
pd(x);
int mid=(l+r)>>1;
if(pos<=mid)return qry(x<<1,l,mid,pos);
else return qry(x<<1|1,mid+1,r,pos);
return ts[x].val;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=0;i>a[i];
for(int i=0;i::iterator it=mp.begin();it!=mp.end();it++){
it->second=cnt;
pos[cnt]=it->first;
cnt++;
}
build(1,0,n-1);
int tmp=1;
for(int i=0;i=a[i-1]){
int pos=mp[a[i]],val=ts[1].val;
upd(1,0,n-1,0,pos,(mod-val)%mod);
}else{
int lp=mp[a[i-1]],np=mp[a[i]],val=ts[1].val;
upd(1,0,n-1,0,np,(mod-val)%mod);
mdy(1,0,n-1,np+1,lp);
}
tmp=-tmp;
}
}
int ans=ts[1].val;
ans=(ans*tmp+mod)%mod;
cout< sol2
用 \(dp(i)\) 记录以 \(i\) 结尾的方案书 . 考虑容斥 ，
考虑把 \(n\) 分成 \(k\) 个段，每个段中数值相同，那么就是至少有 \(n-k\) 个位置是相同的方案数 .
枚举 \(b_{i-1}=b_{i}\) 的个数是 \(k\) . 那么容斥的系数就是 \((-1)^{n-k}\) ，考虑把 \((-1)^n\) 提出来，剩下 \((-1)^{-k}=(-1)^k\) 分配到每个区间中 . 得到转移柿子 :
\[dp(i)=-\sum\limits_{j=1}^{i}\min\limits_{k=1}^{j}dp(j-1) \]这个 \(\min\) 显然可以单调栈处理 .
时间复杂度 : \(O(n)\)
空间复杂度 : \(O(n)\)
code
#include
using namespace std;
const int N=5e5+10;
const int mod=998244353;
int n;
int a[N],dp[N];
stack > >s;
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
dp[0]=1;
int res=0;
for(int i=1;i<=n;i++){
int sum=1ll*a[i]*dp[i-1]%mod;
int tmp=dp[i-1];
res=(res+sum)%mod;
while(!s.empty()&&s.top().first>a[i]){
sum=(sum+1ll*s.top().second.first*a[i]%mod)%mod;
res=(res-s.top().second.second+mod)%mod;
res=(res+1ll*s.top().second.first*a[i]%mod)%mod;
tmp=(tmp+s.top().second.first)%mod;
s.pop();
}
s.push(make_pair(a[i],make_pair(tmp,sum)));
dp[i]=(mod-res)%mod;
}
int ans=dp[n];
if(n&1)ans=(mod-ans)%mod;
cout<