首页 > 代码库 > swjtu 2389 The Trip On Abandoned Railway

swjtu 2389 The Trip On Abandoned Railway

2024-09-22 16:58:20   214人阅读

题目链接 http://swjtuoj.cn/problem/2389/

题意：给你n个车站 每个车站有一些鬼

给你两种操作

op == 1  给你x-n增加一个等差数列的值（x位置增加y x+1位置增加y+d x+2位置增加x+2d ）

op == 2 输出x位置的值 然后把x位置的值置零
思路： 定义一个结构题

pos标记 每次op=1操作的位置
lazy标记 每次op=1的首项
t    标记 每次op=1的操作次数
对于每次操作 我们只需要进行区间叠加
val+= （t*x（位置）-pos）*d+lazy

所以可以转变为一个区间叠加的问题

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const LL MOD =1e9+7;
const int maxn = 100010;
struct node
{
    int l,r;
    LL pos,t,lazy;
    LL val;
}tree[maxn<<2];
int n,m;LL d;
int a[maxn];
void build(int root,int l,int r)
{
    tree[root].l=l;tree[root].r=r;
    tree[root].pos=tree[root].t=tree[root].lazy=0;
    if(tree[root].l == tree[root].r)
    {
        tree[root].val=a[l];
    }
    else
    {
        int mid=(l+r)>>1;
        build(root<<1,l,mid);
        build(root<<1|1,mid+1,r);
    }
}
void push_down(int root)
{
    if(tree[root].l == tree[root].r)
    {
        tree[root].val+=(tree[root].r*tree[root].t-tree[root].pos)*d+tree[root].lazy;
        tree[root].val%=MOD;
    }
    else
    {
        tree[root<<1].pos   +=tree[root].pos;
        tree[root<<1|1].pos +=tree[root].pos;
        tree[root<<1].t     +=tree[root].t;
        tree[root<<1|1].t   +=tree[root].t;
        tree[root<<1].lazy  +=tree[root].lazy;
        tree[root<<1|1].lazy+=tree[root].lazy;
    }
    tree[root].pos=tree[root].t=tree[root].lazy=0;
}
void update(int root,int l,int r,LL pos,LL k)
{
    if(tree[root].t) push_down(root);
    if(l <= tree[root].l && tree[root].r <= r)
    {
        tree[root].pos+=l;
        tree[root].t+=1;
        tree[root].lazy+=k;
    }
    else
    {
        int mid=(tree[root].l+tree[root].r)>>1;
        if(l <= mid)
            update(root<<1,l,r,pos,k);
        if(r >  mid)
            update(root<<1|1,l,r,pos,k);
    }
}
LL querry(int root,int pos)
{
    if(tree[root].t) push_down(root);
    if(tree[root].l == tree[root].r)
    {
        LL ret=tree[root].val;
        tree[root].val=0;
        return ret;
    }
    else
    {
        int mid=(tree[root].l+tree[root].r)>>1;
        if(pos <= mid)
            return querry(root<<1,pos);
        else
            return querry(root<<1|1,pos);
    }
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%lld",&n,&m,&d);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            int op;scanf("%d",&op);
            if(op == 1)
            {
                int pos;LL k;scanf("%d%lld",&pos,&k);
                update(1,pos,n,(LL)pos,k);
            }
            else
            {
                int pos;scanf("%d",&pos);
                LL ret=querry(1,pos);
                printf("%lld\n",ret);
            }
        }
    }
    return 0;
}

 

swjtu 2389 The Trip On Abandoned Railway


联系
我们