P1198 JSOI2008最大数


这道题其实就是线段树单点修改区间查询,但开了long long scanf一定要用lld啊 调了半天,真是绝望

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
const int inf=-0x3f3f3f3f;
int m,d,len=0;
long long temp=0;
struct node{
    int l,r,dat;
}t[maxn*4];
void build(int id,int l,int r)
{
    t[id].l=l,t[id].r=r;
    if(l==r)
    {
        t[id].dat=0;
        return;
    }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    t[id].dat=max(t[id<<1].dat,t[id<<1|1].dat);
}
void change(int id,int x,int p)
{
    if(t[id].l==t[id].r)
    {
        t[id].dat=p;
        return;
    }
    int mid=(t[id].l+t[id].r)>>1;
    if(x<=mid) change(id<<1,x,p);
    else change(id<<1|1,x,p);
    t[id].dat=max(t[id<<1].dat,t[id<<1|1].dat);
}
long long query(int id,int l,int r)
{
    if(l<=t[id].l&&r>=t[id].r) return t[id].dat;
    int mid=(t[id].l+t[id].r)>>1;
    long long res=inf;
    if(l<=mid) res=max(res,query(id<<1,l,r));
    if(r>mid) res=max(res,query(id<<1|1,l,r));
    return res;
}
int main()
{
    scanf("%d%d",&m,&d);
    build(1,1,m);
    while(m--)
    {
        long long x;char c;
        cin>>c,scanf("%lld",&x);
        if(c=='A') 
        {
            len++;
            change(1,len,(x+temp)%d);
        }
        else
        {
            if(x==0) printf("0\n");
            else
            {
                temp=query(1,len-x+1,len);
                printf("%lld\n",temp);
            }

        }
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
POJ 3662 Telephone Lines POJ 3662 Telephone Lines
这道题有两种解法,第二种是以后会写的动态规划,还有就是二分加最短路,这是最小化图中第k大的值,不难想到二分花费,对于大于此花费边权为1,其他为0,之后dijkstra最短路是否小于等于k,来进行判断,其实只有0和1的边也可以通过双端队列bf
2019-07-05
下一篇 
SP1716 GSS3 - Can you answer these queries III SP1716 GSS3 - Can you answer these queries III
这是一道比较复杂的线段树维护题目,由于最大字段和是满足区间可加性的,所以可以通过线段树来维护 void update(int id) { t[id].sum=t[id<<1].sum+t[id<<1|1].s
2019-07-05
  目录