首页 > 其他 > 详细

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

时间:2019-06-19 20:57:57      阅读:220      评论:0      收藏: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));
    }
}

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

原文:https://www.cnblogs.com/BAJimH/p/11054456.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!