題目

序列a1,a2,...ap是好序列，

當且僅當p>=1且任意i∈[1,p)，有或

給定長為n(n<=1e5)的序列a1,...,an(1<=ai<=n)，q(q<=2e5)次詢問

每次詢問給定k,l,r(1<=k<=n,1<=l<=r<=n)，

詢問區間[l,r]內的子序列中有多少個是好序列

答案對1e9+7取模

思路來源

比賽幾分鐘后才做出來，這種題做過無數次了，次次被卡

題解

一開始想著邊轉移，但是不行，需要有一個末態的概念

所以，需要按點轉移，>=k記為狀態1，<k記為狀態0，

子序列矩陣可以0轉移到0，1轉移到1，0轉移到1，1轉移到0，

其中，前兩種表示本次不取，后兩種只能同時有一個存在，表示之前取的是0/1，本次取的是1/0

將k離線，建立線段樹矩陣，在ai<k時對ai單點反轉c[0][1]和c[1][0]

注意到，c[0][0]和c[1][1]均有為空的一種方案，所以答案需要恒減2

最后幾分鐘就是這里沒想清楚

代碼

#include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=2e5+10,mod=1e9+7; const int INF=0x3f3f3f3f; int n,q,l,r,v,a[N],ans[M]; vector<int>add[N]; struct mat{const static int MAXN = 2;int c[MAXN][MAXN];int m, n;mat(){memset(c,0,sizeof (c));}mat(int a, int b) : m(a), n(b) {memset(c, 0, sizeof (c));}void reset(int a,int b){m=a; n=b;}void clear(){memset(c, 0, sizeof(c)); }mat operator + (const mat& temp) {mat ans(m, temp.n);for (int i = 0; i < m; i ++)for (int j = 0; j < temp.n; j ++) {for (int k = 0; k < n; k ++){ans.c[i][j] = (ans.c[i][j] + 1ll * c[i][k] * temp.c[k][j] %mod)%mod;}}return ans;} }dat[N*4],y; struct node{int id,l,r;node(){}node(int a,int b,int c):id(a),l(b),r(c){} }; vector<node>f[N]; void pushup(int p){dat[p]=dat[p<<1]+dat[p<<1|1]; } void init(int p,int l,int r){dat[p].c[0][1]=1;dat[p].c[1][1]=1;dat[p].c[0][0]=1;dat[p].c[1][0]=0; } void build(int p,int l,int r){dat[p].reset(2,2);if(l==r){init(p,l,r);return;}int mid=(l+r)/2;build(p<<1,l,mid);build(p<<1|1,mid+1,r);pushup(p); } void chg(int p,int l,int r,int pos){if(l==r){dat[p].c[1][0]=1;dat[p].c[0][1]=0;return;} int mid=(l+r)/2;if(pos<=mid)chg(p<<1,l,mid,pos);else chg(p<<1|1,mid+1,r,pos);pushup(p); } mat ask(int p,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return dat[p];int mid=(l+r)/2;if(ql>mid)return ask(p<<1|1,mid+1,r,ql,qr);if(qr<=mid)return ask(p<<1,l,mid,ql,qr);return ask(p<<1,l,mid,ql,mid)+ask(p<<1|1,mid+1,r,mid+1,qr); } int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;++i){scanf("%d",&a[i]);add[a[i]].push_back(i);}build(1,1,n);for(int i=1;i<=q;++i){int k,l,r;scanf("%d%d%d",&k,&l,&r);f[k].push_back(node(i,l,r));}for(int i=1;i<=n;++i){for(auto &x:f[i]){int id=x.id,l=x.l,r=x.r;y=ask(1,1,n,l,r);ans[id]=(1ll*y.c[0][0]+y.c[0][1]+y.c[1][0]+y.c[1][1])%mod;ans[id]=(ans[id]+mod-2)%mod;}for(auto &v:add[i]){chg(1,1,n,v);}}for(int i=1;i<=q;++i){printf("%d\n",ans[i]);}return 0; }

總結

以上是生活随笔為你收集整理的2022 百度之星程序设计大赛复赛 D.子序列2(动态dp/线段树维护矩阵)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。