[训练指南] 复习线段树区间修改 基本操作题 UVa11992

感觉真的是被期末考试掏空身体了,,,这个代码自己写完之后调试出来5个bug,没办法对照着lrj的代码一行一行看才找到所有错误。。都是泪啊

题也就很简单,本身都是基础操作没什么可说的,只是set标记优先级在add标记之上罢了

#include 
#include 
#include 
#include
#include
#include
#include
#include
#include
//#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=2e6+5;
const int maxq=2e5+5;
const int maxb=20*maxq;
const int MOD=1e9+7;

int op,x1,y1,x2,y2,v,ql,qr;

struct IntervalTree
{
    int su[maxn],mi[maxn],ma[maxn],setv[maxn],addv[maxn];

    void maintain(int o,int l,int r)
    {
        int lc=o*2,rc=o*2+1;
        if(r>l)
        {
            mi[o]=min(mi[lc],mi[rc]);
            ma[o]=max(ma[lc],ma[rc]);
            su[o]=su[lc]+su[rc];
        }
        if(setv[o]>=0)
        {
            mi[o]=ma[o]=setv[o];
            su[o]=setv[o]*(r-l+1);
        }
        if(addv[o])
        {
            mi[o]+=addv[o];
            ma[o]+=addv[o];
            su[o]+=addv[o]*(r-l+1);
        }
    }

    void pushdown(int o)
    {
        int lc=o*2,rc=o*2+1;
        if(setv[o]>=0)
        {
            setv[lc]=setv[rc]=setv[o];
            addv[lc]=addv[rc]=0;
            setv[o]=-1;
        }
        if(addv[o])
        {
            addv[lc]+=addv[o];
            addv[rc]+=addv[o];
            addv[o]=0;
        }
    }

    void update(int o,int l,int r)
    {
        if(ql<=l&&r<=qr)
        {
            if(op==1)
                addv[o]+=v;
            else
            {
                setv[o]=v;
                addv[o]=0;//error?
            }
        }
        else
        {
            pushdown(o);//error3??
            int mid=l+(r-l)/2;
            if(ql<=mid)update(o*2,l,mid);else maintain(o*2,l,mid);//error2??
            if(mid

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据