P2667防御分块做法

· · 题解

Page 0

为什么都没有分块的题解啊。

题目感觉难度不是绿题，建议升蓝。

Page 1

看到这题，我首先想到的是线段树，然后感觉不可做。

我果然太菜了

一看数据范围：10^5，分块好像能过。

这道题最大的问题是攻击了一次打了大标记后可能有一些盾碎掉了，下一次应该造成双倍伤害，但是却没有及时标记。

考虑维护块内最小值（下文记作 minn），如果区间攻击的 tag < minn，那么一定不会有盾被打碎。

如果 tag \geq minn 那么就把这一个整块的标记都下传，进行暴力重构。

有些人可能会觉得时间复杂度不对，但是其实是正确的。

因为每一个盾只会碎一次，所以每一个盾的复杂度加成最多是 \sqrt n，所以碎盾的复杂度总和最多是 O(n \times \sqrt n) 级别。

对于散块，注意更改了之后维护 minn，代码中用 a 来维护盾的血量，当一个盾被打破后，把它的血量设置成无限大。

然后就是基本操作了。

注意，假如盾的血量是 1，然后它收到了 114514 点伤害，它也只是受到 114514 点伤害的，而不是 229018 点或其他，所以要注意处理 tag 和当前攻击伤害的关系。

这道题开了 long long 之后好像不需要中间取模，最后再取模就可以。

具体实现细节见代码：

码风略丑，勿喷

#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
//a 是盾的血量，tg 是伤害标记， minn 是块内最小值，b是答案
int a[1000001],tg[1000001],all,minn[10001],b[1000001],x,t,n,m,l,r,k;
inline int read()
{
    int ans=0;char ch=getchar();
    while((ch>'9')||(ch<'0'))ch=getchar();
    while((ch>='0')&&(ch<='9'))ans=ans*10+ch-'0',ch=getchar();
    return ans;
}
char opt;
signed main()
{
    n=read();m=read();t=sqrt(n);
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)if(a[i]==0)a[i]=9999999999999999;
    for(int i=1;i<=n;i+=t)minn[(i-1)/t+1]=9999999999999999;
    for(int i=1;i<=n;i++)minn[(i-1)/t+1]=min(minn[(i-1)/t+1],a[i]);
    //不要忘记初始化，a一开始可能就是0
    while(m--)
    {
        cin>>opt;
        if(opt=='Q')
        {
            x=read();
            if(a[x]==9999999999999999)all=(all+(b[x]+tg[(x-1)/t+1]*2)%1000000009)%1000000009;
            else all=(all+(b[x]+tg[(x-1)/t+1])%1000000009)%1000000009;
            //cout<<all<<endl;
        }
        else
        {
            l=read();r=read();x=read();
            if((l-1)/t+1==(r-1)/t+1)//如果在同一块内
            {
                bool minf=0;//minf 表示当前块是否需要重构 ，以下同上 
                for(int i=l;i<=r;i++)
                {
                    if(a[i]==9999999999999999)b[i]+=2*x;//如果盾已经碎了 
                    else b[i]+=x;
                    if(a[i]!=9999999999999999)
                    a[i]-=x;
                    minn[(l-1)/t+1]=min(minn[(l-1)/t+1],a[i]);//不要忘记维护 minn 
                    if(a[i]<=tg[(l-1)/t+1])minf=1;
                }
                if(minf)
                {
                    minn[(l-1)/t+1]=9999999999999999;
                    for(int i=(l-1)/t*t+1;i<=min((l-1)/t*t+t,n);i++)
                    {
                        if(a[i]==9999999999999999)b[i]+=2*tg[(l-1)/t+1];
                        else b[i]+=tg[(l-1)/t+1];
                        if(a[i]!=9999999999999999)
                        a[i]-=tg[(l-1)/t+1];
                        if(a[i]<=0)a[i]=9999999999999999;
                        minn[(l-1)/t+1]=min(minn[(l-1)/t+1],a[i]);
                    }
                    tg[(l-1)/t+1]=0;//tag 不要忘记清空 
                }
            }
            else
            {
                //处理左边散块 
                bool minf=0;
                for(int i=l;i<=min(((l-1)/t+1)*t,n);i++)
                {
                    if(a[i]==9999999999999999)b[i]+=x*2;
                    else b[i]+=x;
                    if(a[i]!=9999999999999999)
                    a[i]-=x;
                    minn[(l-1)/t+1]=min(minn[(l-1)/t+1],a[i]);
                    if(a[i]<=tg[(l-1)/t+1])minf=1;
                }
                if(minf)
                {
                    minn[(l-1)/t+1]=9999999999999999;
                    for(int i=(l-1)/t*t+1;i<=min(((l-1)/t+1)*t,n);i++)
                    {
                        if(a[i]==9999999999999999)b[i]+=tg[(l-1)/t+1]*2;
                        else b[i]+=tg[(l-1)/t+1];
                        if(a[i]!=9999999999999999)
                        a[i]-=tg[(l-1)/t+1];
                        if(a[i]<=0)a[i]=9999999999999999;
                        minn[(l-1)/t+1]=min(minn[(l-1)/t+1],a[i]);
                    }
                    tg[(l-1)/t+1]=0;
                }
                //中间整块 
                for(int i=(l-1)/t+2;i<(r-1)/t+1;i++)
                {
                    tg[i]+=x;
                    if(tg[i]>=minn[i])
                    {
                        minn[i]=9999999999999999;
                        for(int j=(i-1)*t+1;j<=min((i-1)*t+t,n);j++)
                        {
                            if(a[j]==9999999999999999)b[j]+=tg[i]*2;
                            else b[j]+=tg[i];
                            if(a[j]!=9999999999999999)
                            a[j]-=tg[i];
                            if(a[j]<=0)a[j]=9999999999999999;
                            minn[i]=min(minn[i],a[j]);
                        }
                        tg[i]=0;
                    }
                }
                minf=0;
                //右边散块 
                for(int i=(r-1)/t*t+1;i<=r;i++)
                {
                    if(a[i]==9999999999999999)b[i]+=x*2;
                    else b[i]+=x;
                    if(a[i]!=9999999999999999)
                    a[i]-=x;
                    minn[(r-1)/t+1]=min(minn[(r-1)/t+1],a[i]);
                    if(a[i]<=tg[(r-1)/t+1])minf=1;
                }
                if(minf)
                {
                    minn[(r-1)/t+1]=9999999999999999;
                    for(int i=(r-1)/t*t+1;i<=min((r-1)/t*t+t,n);i++)
                    {
                        if(a[i]==9999999999999999)b[i]+=tg[(r-1)/t+1]*2;
                        else b[i]+=tg[(r-1)/t+1];
                        if(a[i]!=9999999999999999)
                        a[i]-=tg[(r-1)/t+1];
                        if(a[i]<=0)a[i]=9999999999999999;
                        minn[(r-1)/t+1]=min(minn[(r-1)/t+1],a[i]);
                    }
                    tg[(r-1)/t+1]=0;
                }
            }
        }
    }
    printf("%lld",all%1000000009);
    return 0;
}