BZOJ4241: 历史研究【回滚莫队】

4241: 历史研究

【题目描述】

传送门

【题解】

考虑莫队做法,突然发现这题对于插入可以做到O(1),但是删除的话就特别烦了。
这里引入一个特殊的莫队做法,回滚莫队,就是将删除看成插入来做。
首先我们知道每块内R肯定是递增的,所以R是可以O(1)插入,如果进入下一块的话,直接清空数组,R从L-1开始。
但是L是会乱动的,所以我们每次\sqrt{n}直接暴力更新L就可以了,最后回滚到之前状态。

代码如下

#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=100005;
typedef long long LL;
int n,m,K,tim,vis[MAXN],a[MAXN],block[MAXN],b[MAXN];LL MX,Ans[MAXN],hsh[MAXN];
struct xcw{
    int L,R,B,id;
    bool operator <(const xcw b)const{return (block[L]<block[b.L])||(block[L]==block[b.L]&&R<b.R);}
}W[MAXN];
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=ret*10+ch-48;
    return f?ret:-ret;
}
void print(LL x){if(x>9) print(x/10);putchar(x%10+48);}
int main(){
//  freopen("4241.in","r",stdin);
//  freopen("4241.out","w",stdout);
    n=read(),m=read();K=sqrt(n);
    for(int i=1;i<=n;i++) b[i]=a[i]=read();
    sort(b+1,b+1+n);int D=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+D,a[i])-b;
    for(int i=1;i<=n;i++) block[i]=(i-1)/K+1;
    for(int i=1;i<=m;i++) W[i]=(xcw){read(),read(),0,i},W[i].B=block[W[i].L]*K+1;
    sort(W+1,W+1+m);
    for(int i=1,L=0,R=0;i<=m;i++){
        if(L!=W[i].B) tim++,MX=0,L=W[i].B,R=W[i].B-1;
        while(R<W[i].R){
            ++R;
            if(vis[a[R]]!=tim) hsh[a[R]]=0;
            hsh[a[R]]+=b[a[R]],vis[a[R]]=tim;
            if(hsh[a[R]]>MX) MX=hsh[a[R]];
        }
        LL Now=MX;int END=min(W[i].R,L-1);
        for(int j=W[i].L;j<=END;j++){
            if(vis[a[j]]!=tim) hsh[a[j]]=0;
            hsh[a[j]]+=b[a[j]],vis[a[j]]=tim;
            if(hsh[a[j]]>Now) Now=hsh[a[j]];
        }
        Ans[W[i].id]=Now;
        for(int j=W[i].L;j<=END;j++) hsh[a[j]]-=b[a[j]];
    }
    for(int i=1;i<=m;i++) print(Ans[i]),putchar('\n');
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部