【杂题】[CodeForces 1172F] Nauuo and Bug【数据结构】【线段树】

小咪咪 2021-12-11 11:37 244阅读 0赞

## Description ##

给出一个长度为n的序列a和一个整数p  
有m组询问，每组询问给出一个区间\\(\[l,r\]\\)  
你需要给出下面这个过程的结果

ans = 0 
    for i from l to r
    {
        ans = ans + a[i]
        if ans > p then ans = ans - p;
    }
    return ans

\\(n\\leq 10^6\\)  
\\(m<=2\\times10^5\\)  
\\(p\\leq10^9\\)  
\\(-10^9\\leq a\_i\\leq10^9\\)

## Solution ##

显然一个区间内至多只会减区间长度次p  
也就是说如果我们设一个函数\\(f(x)\\)为初始为x，经过区间\\(\[l,r\]\\)后的答案，那么\\(f(x)\\)显然由\\(r-l+2\\)段斜率为1的一次函数构成，且相邻两段之间截距差为p

更进一步的，可以发现每一段的长度是\\(O(p)\\)的

那么我们可以考虑用线段树维护函数，对于每个线段树区间记下每段的端点，查询很简单，直接从0开始加上这一段的贡献，并在下一个区间中二分属于那一段即可。

关键是建树  
考虑左子区间和右子区间已经建好，考虑将它们合并，实际上就是一个函数复合的过程。  
具体实现来说，枚举左子区间的所有段，计算出相应的值域区间，然后右边用一个指针找合法的右段。  
由于每一段的长度均为\\(O(p)\\)，因此每次指针动的位置数是常数级的。

总的时间复杂度为\\(O(n\\log n+m\\log^2 n)\\)  
可以参考程序。

## Code ##

//Copyright Reserved by BAJim_H
    #include <bits/stdc++.h>
    #define fo(i,a,b) for(int i=a;i<=b;++i)
    #define fod(i,a,b) for(int i=a;i>=b;--i)
    typedef long long LL;
    const int N=2000005;
    const LL INF=(LL)1e16;
    using namespace std;
    vector<LL> f[N];
    int t[N][2],d[200],a[N],n,n1,mo,q;
    LL sm[N];
    template <class I>
    void read(I &x)
    {
        x=0;char ch=getchar();I v=1;
        while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
        if(ch=='-') v=-1,ch=getchar();
        while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
        x=x*v;
    }
    void build(int k,int l,int r)
    {
        if(l==r) {f[k].push_back(-INF),f[k].push_back(mo-a[l]);sm[k]=a[l];return;}
        int mid=(l+r)>>1;
        t[k][0]=++n1,build(t[k][0],l,mid);
        t[k][1]=++n1,build(t[k][1],mid+1,r);
        int x=t[k][0],y=t[k][1],rx=f[x].size(),ry=f[y].size();
        f[k].resize(rx+ry-1,INF);       
        for(int i=0,j=0;i<rx;++i)
        {
            LL xl=f[x][i],xr=(i+1!=rx)?f[x][i+1]-1:INF,yl=xl+sm[x]-(LL)i*mo,yr=xr+sm[x]-(LL)i*mo;
            while(j>0&&f[y][j]>yl) j--;
            while(j<ry&&f[y][j]<=yl) j++;
            if(j) j--;
            while(j<ry&&f[y][j]<=yr) f[k][i+j]=min(f[k][i+j],max(xl,f[y][j]-sm[x]+(LL)i*mo)),j++;
        }
        f[k][0]=-INF;
        sm[k]=sm[t[k][0]]+sm[t[k][1]];
    }
    void find(int k,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y) {d[++d[0]]=k;return;}
        int mid=(l+r)>>1;
        if(x<=mid) find(t[k][0],l,mid,x,y);
        if(y>mid) find(t[k][1],mid+1,r,x,y);
    }
    LL query(int x,int y)
    {
        d[0]=0;find(1,1,n,x,y);
        LL c=0;
        fo(i,1,d[0]) 
            c+=sm[d[i]]-(LL)mo*(upper_bound(f[d[i]].begin(),f[d[i]].end(),c)-f[d[i]].begin()-1);
        return c;
    }
    int main()
    {
        cin>>n>>q>>mo;
        fo(i,1,n) read(a[i]);
        n1=1;
        build(1,1,n); 
        fo(i,1,q)
        {
            int x,y;
            read(x),read(y);
            printf("%lld\n",query(x,y));
        }
    }

转载于:https://www.cnblogs.com/BAJimH/p/11054456.html