如圖：一道很裸的回滾莫隊(duì)，注意加入的操作和回滾的操作就好了。

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #include <bitset> #include <complex> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define sc second #define pb push_back #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; const ll mod=998244353; const ll N =2e6+10; const ll M=2e6+10; const double eps = 1e-6; const double PI=acos(-1); ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);} ll re(){ll x;scanf("%lld",&x);return x;} int dx[8]= {1,0,-1,0,1,1,-1,-1}, dy[8] = {0,1,0,-1,1,-1,1,-1}; ll qk(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;} ll len,n,m; ll get(ll x) {return x/len;} struct p{ll l,r,k,id;bool operator <(const p &M)const{return make_pair(get(l),r)<make_pair(get(M.l),M.r);} }q[N]; struct sta{ll sum,pos; }sta[N]; ll tm;//當(dāng)前時(shí)間戳 ll L[N],R[N]; ll a[N]; ll ans[N]; ll sum; ll cnt[N]; void add(ll x){sta[tm++]={sum,x};cnt[x]++;if(cnt[x]==1){L[x] = R[x] = x;if(L[x-1]) L[x]=L[x-1];if(R[x+1]) R[x]=R[x+1];if(R[L[x]])R[L[x]]=R[x];if(L[R[x]])L[R[x]]=L[x];sum=max(sum,R[x]-L[x]+1);} } void Back(int x){while(tm>x){sum=sta[--tm].sum;ll x=sta[tm].pos;cnt[x]--;if(cnt[x]==0){L[x]=R[x]=0;if(L[x-1])R[L[x-1]]=R[x-1]=x-1;if(R[x+1])L[R[x+1]]=L[x+1]=x+1;}} } void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];len=sqrt(n);for(int i=1;i<=m;i++) {cin>>q[i].l>>q[i].r>>q[i].k;q[i].id=i;}sort(q+1,q+1+m);ll x=0;while(x<=m){for(int i=0;i<=n;i++) cnt[i]=L[i]=R[i]=0;sum=0,tm=0;ll y=x;while(y<=m&&get(q[y].l)==get(q[x].l)) y++;ll right=get(q[x].l)*len+len-1;while(x<y&&q[x].r<=right){ll id=q[x].id,l=q[x].l,r=q[x].r,k=q[x].k;for(int i=l;i<=r;i++) add(a[i]);ll ans1=sum;ll inv=1;for(int i=1;i<=k-1;i++){inv=inv*(n+1)%mod;add(a[l-i]);add(a[r+i]);ans1=(ans1+sum*inv%mod)%mod;}ans[id]=ans1;Back(0);x++;sum=0;}int i,j=right;while(x<y){i=right+1;ll id=q[x].id,l=q[x].l,r=q[x].r,k=q[x].k;while(j<r) add(a[++j]);ll now=tm;while(i>l) add(a[--i]);ll ans1=sum;ll inv=1;for(int w=1;w<=k-1;w++){inv=(inv*(n+1))%mod;add(a[l-w]);add(a[r+w]);ans1=(ans1+sum*inv%mod)%mod;}ans[id]=ans1;Back(now);x++;}}for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); }int main() {int t=1;while(t--) solve();return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021牛客第五场 I.Interval Queries-回滚莫队的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。