[JSOI2008]最大数

野性酷女 2021-12-10 10:15 145阅读 0赞

[题目传送门][Link 1]

这道题需要解决的是区间求值和单点修改，可以用线段树求解，首先构造一颗\[1,m\]的“空树”（序列至多有m个数），即每个节点维护的信息均为0，新建一个变量sum表示序列中实际数的个数，每次修改第sum个节点，最后n个数就是\[sum-n+1,sum\]，简单维护即可。

下面给出参考代码：

#include<iostream>
    #include<cstring>
    using namespace std;
    struct node
    {
        int l,r,maxn;
    }tree[800008];
    int m,d,n,t,sum;
    char q;
    void build(int k,int l,int r)
    {
        tree[k].maxn=-21374404;tree[k].l=l;tree[k].r=r;
        if(l==r)return;
        int mid=(l+r)/2;
        build(k*2,l,mid);
        build(k*2+1,mid+1,r);
    }
    void add(int k,int l,int r)
    {
        int ll=tree[k].l,rr=tree[k].r;
        if(ll==rr)
        {
            tree[k].maxn=n;
            return;
        }
        int mid=(ll+rr)/2;
        if(sum<=mid)add(k*2,l,r);
        else add(k*2+1,l,r);
        tree[k].maxn=max(tree[k*2].maxn,tree[k*2+1].maxn)%d;
    }
    int query(int k,int l,int r)
    {
        int ll=tree[k].l,rr=tree[k].r;
        if(ll>=l&&rr<=r)
        {
            return tree[k].maxn;
        }
        int mid=(ll+rr)/2;
        int lc=-123456,rc=-123456;
        if(sum-n+1<=mid)lc=query(k*2,l,r);
        if(sum>mid)rc=query(k*2+1,l,r);
        return max(lc,rc)%d;
    }
    void check(int l,int r,int k)
    {
        if(l==r)
        {
            cout<<tree[k].maxn<<" ";
            return;	
        }
        int mid=(l+r)/2;
        check(l,mid,k*2);
        check(mid+1,r,k*2+1);
        return;
    }
    int main()
    {
        cin>>m>>d;
        build(1,1,m);
        for(int i=1;i<=m;i++)
        {
            cin>>q>>n;
            if(q=='A')
            {
                n+=t;
                n%=d;
                sum++;
                add(1,1,sum);
            }
            else
            {
                t=query(1,sum-n+1,sum)%d;
                cout<<t<<endl;
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/szmssf/p/11079547.html

[Link 1]: https://www.luogu.org/problemnew/show/P1198