CSP模拟26
可做场，拜谢fengwu老师。
A. Reversi (AGC031B)
题目链接
一眼切了
设 $ dp_i $ 表示考虑到第 $ i$ 个石头的总方案数。
可由两种情况转移，不选择染色和选择染色，不染色直接由 $ dp_{i-1} $ 转移过来 ，染色由上一个和当前颜色相同的的石头转移过来，相当于把两个石子之间的染色。因为一个石子被染色后就不可以在给别的石子染色。
设 $ h_i $表示和当前石子颜色相同的最近的石子的位置。
则：
\[dp_i=dp_{i-1} + dp_{i-h[i]}
\]
复杂度为 $ O(n) $
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
const int MAXN=5e6+10;
const int mod=1e9+7;
using namespace std;
inline int read() {
int f=1,x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') {
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return f*x;
}
int n;
int a[MAXN];
int cnt[MAXN], beh[MAXN];
int dp[MAXN];
signed main() {
n=read();
for(int i=1;i<=n;i++) {
a[i]=read();
beh[i]=cnt[a[i]];
cnt[a[i]]=i;
}
dp[0]=0, dp[1]=1;
for(int i=2;i<=n;i++) {
dp[i]=dp[i-1]%mod;
if(beh[i]+1==i) continue;
dp[i]=(dp[i]+dp[beh[i]])%mod;
}
printf("%lld",dp[n]%mod);
return 0;
}
B. Non-Decreasing Dilemma
题目链接
比较普通的线段树维护，考虑维护区间左右两端の最长上升字串，对于完整地上升字串 ，设长度为 $ len$ 则对答案地贡献为 $ len(len-1)/2 $ ,合并时判断即可。
复杂度：修改为 $ O( \log n) $ ,查询为 $ O(\log n) $ ，总复杂度为 $ O(q\log n)$
点击查看代码
#include <iostream>
#include <cstdio>
#define int long long
const int MAXN=2e5+10;
using namespace std;
inline int read() {
int f=1,x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') {
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return f*x;
}
int n,q;
int a[MAXN];
struct Tree {
int l,r;
int vl,vr;
int ll,lr;
int sum,len;
}t[MAXN<<2];
void push_up(int k) {
t[k].len=t[k<<1].len+t[k<<1|1].len;
t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
t[k].vl=t[k<<1].vl ,t[k].vr=t[k<<1|1].vr;
t[k].ll=t[k<<1].ll , t[k].lr=t[k<<1|1].lr;
if(t[k<<1].vr<=t[k<<1|1].vl) {
int len=t[k<<1].lr+t[k<<1|1].ll;
if(t[k<<1].lr!=t[k<<1].len && t[k<<1|1].ll!=t[k<<1|1].len) {
t[k].sum+=(len*(len-1)/2);
}
if(t[k<<1].ll==t[k<<1].len) {
t[k].ll=len;
}
if(t[k<<1|1].lr==t[k<<1|1].len) {
t[k].lr=len;
}
}
else {
if(t[k<<1].lr!=t[k<<1].len) {
int len=t[k<<1].lr;
t[k].sum+=(len*(len-1)/2);
}
if(t[k<<1|1].ll!=t[k<<1|1].len) {
int len=t[k<<1|1].ll;
t[k].sum+=(len*(len-1)/2);
}
}
}
void build(int k,int l,int r) {
t[k].l=l ,t[k].r=r;
if(l==r) {
t[k].len=1;
t[k].sum=0;
t[k].vl=t[k].vr=a[l];
t[k].ll=t[k].lr=1;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void change(int k,int l,int r,int pos,int val) {
if(l==r) {
t[k].vl=t[k].vr=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid) change(k<<1,l,mid,pos,val);
else change(k<<1|1,mid+1,r,pos,val);
push_up(k);
}
Tree query(int k,int l,int r,int L,int R) {
if(L==l && r==R) {
return t[k];
}
int mid=(l+r)>>1;
if(mid<L) {
return query(k<<1|1,mid+1,r,L,R);
}
else if(mid>=R) {
return query(k<<1,l,mid,L,R);
}
else {
Tree x,y,res;
x=query(k<<1,l,mid,L,mid);
y=query(k<<1|1,mid+1,r,mid+1,R);
res.len=x.len+y.len;
res.sum=x.sum+y.sum;
res.vl=x.vl ,res.vr=y.vr;
res.ll=x.ll ,res.lr=y.lr;
if(x.vr<=y.vl) {
int len=x.lr+y.ll;
if(x.lr!=x.len && y.ll!=y.len) {
res.sum+=(len*(len-1)/2);
}
if(x.ll==x.len) {
res.ll=len;
}
if(y.lr==y.len) {
res.lr=len;
}
}
else {
if(x.lr!=x.len) {
int len=x.lr;
res.sum+=(len*(len-1)/2);
}
if(y.ll!=y.len) {
int len=y.ll;
res.sum+=(len*(len-1)/2);
}
}
return res;
}
}
void solve1() {
for(int g=1;g<=q;g++) {
int op=read();
if(op==1) {
int x=read() ,y=read();
a[x]=y;
}
if(op==2) {
int l=read(),r=read(),ans=0;
int sum=1;
for(int i=l+1;i<=r;i++) {
if(a[i-1]<=a[i]) {
sum++;
}
else {
ans+=((sum-1)*sum)/2;
sum=1;
}
}
ans+=(sum*(sum-1)/2);
printf("%lld\n",ans+(r-l+1));
}
}
}
signed main() {
n=read() ,q=read();
for(int i=1;i<=n;i++) {
a[i]=read();
}
build(1,1,n);
for(int i=1;i<=q;i++) {
int op=read();
if(op==1) {
int x=read() ,y=read();
a[x]=y;
change(1,1,n,x,y);
}
if(op==2) {
int x=read() ,y=read();
Tree res=query(1,1,n,x,y);
int l=res.ll ,r=res.lr ,ans;
if(res.sum==0 && l==res.len && r==res.len) ans=(l*(l-1)/2);
else ans=res.sum+(l*(l-1)/2)+(r*(r-1))/2;
printf("%lld\n",ans+(y-x+1));
}
}
return 0;
}