据说PA的题是不计时限的?

数据:https://sio2.mimuw.edu.pl/c/pa-2015-1/tests/

题意:n块土地,第i块土地第i秒会长出k的杂草

你一共有m次操作

每次操作你会把某个位置的杂草的高度剪到k(注意:如果不足k则不剪)

问每次会剪下多少杂草

所以..

这题是个线段树..

虽然真心感觉这样不太好..好像可以写树状数组..

线段树维护一个tag和一个sum和一个最右边的值max..

不管了能过就行..

这个query包含了修改操作

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[500005];
long long sum_a[500005];
long long sum[1<<21];
long long maxs[1<<21];
long long flag[1<<21];
void build_tree(int num,int l,int r)
{
    sum[num]=0;
    maxs[num]=0;
    flag[num]=-1000000000000000ll;
    if (l==r-1) return;
    int mid=(l+r)/2;
    build_tree(num*2+1,l,mid);
    build_tree(num*2+2,mid,r);
}
void push_down(int num,int l,int r)
{
    if (num>=(1<<20)) return;
    int mid=(l+r)/2;
    if (flag[num]<0)
    {
        if (flag[num]==-1000000000000000ll) return;
        if (flag[num*2+1]>=0) push_down(num*2+1,l,mid);
        if (flag[num*2+2]>=0) push_down(num*2+2,mid,r);
        maxs[num*2+1]+=(-flag[num])*a[mid-1];
        maxs[num*2+2]+=(-flag[num])*a[r-1];
        sum[num*2+1]+=(sum_a[mid]-sum_a[l])*(-flag[num]);
        sum[num*2+2]+=(sum_a[r]-sum_a[mid])*(-flag[num]);
        if (flag[num*2+1]!=-1000000000000000ll)
        {
            flag[num*2+1]+=flag[num];
        }
        else
        {
            flag[num*2+1]=flag[num];
        }
        if (flag[num*2+2]!=-1000000000000000ll)
        {
            flag[num*2+2]+=flag[num];
        }
        else
        {
            flag[num*2+2]=flag[num];
        }
        flag[num]=-1000000000000000ll;
        return;
    }
    maxs[num*2+1]=flag[num];
    flag[num*2+1]=flag[num];
    sum[num*2+1]=(mid-l)*flag[num];
    maxs[num*2+2]=flag[num];
    flag[num*2+2]=flag[num];
    sum[num*2+2]=(r-mid)*flag[num];
    flag[num]=-1000000000000000ll;
}
long long query(int num,int l,int r,long long b,long long past_days)
{
    if (l==r-1)
    {
        long long ans=(a[l]*past_days+sum[num]-b);
        sum[num]=b;
        maxs[num]=b;
        if (ans<0)
        {
            sum[num]+=ans;
            maxs[num]+=ans;
            ans=0;
        }
        return ans;
    }
    int mid=(l+r)/2;
    push_down(num,l,r);
    if (past_days*a[mid-1]+maxs[num*2+1]>b)
    {
        long long ans=query(num*2+1,l,mid,b,past_days);
        ans+=(sum_a[r]-sum_a[mid])*past_days+sum[num*2+2]-b*(r-mid);
        flag[num*2+2]=b;
        maxs[num*2+2]=b;
        sum[num*2+2]=b*(r-mid);
        sum[num]=sum[num*2+1]+sum[num*2+2];
        maxs[num]=maxs[num*2+2];
        return ans;
    }
    else if (past_days*a[r-1]+maxs[num*2+2]>b)
    {
        push_down(num*2+1,l,mid);
        flag[num*2+1]=-past_days;
        sum[num*2+1]+=(sum_a[mid]-sum_a[l])*past_days;
        maxs[num*2+1]+=a[mid-1]*past_days;
        long long ans=query(num*2+2,mid,r,b,past_days);
        sum[num]=sum[num*2+1]+sum[num*2+2];
        maxs[num]=maxs[num*2+2];
        return ans;
    }
    else
    {
        flag[num]=-past_days;
        sum[num]+=(sum_a[r]-sum_a[l])*past_days;
        maxs[num]+=a[r-1]*past_days;
        return 0;
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int i;
    for (i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for (i=0;i<n;i++)
    {
        sum_a[i+1]=sum_a[i]+a[i];
    }
    build_tree(0,0,n);
    long long last_d=0;
    for (i=0;i<m;i++)
    {
        long long d,b;
        cin>>d>>b;
        long long ans=query(0,0,n,b,d-last_d);
        cout<<ans<<'\n';
        last_d=d;
    }
    return 0;
}