快速红包变换 - sxysxy - 338145

记录编号	338145	评测结果	AAAAAAAAAAW
题目名称	快速红包变换	最终得分	90
用户昵称	sxysxy	是否通过	未通过
代码语言	C++	运行时间	0.954 s
提交时间	2016-11-05 08:07:19	内存使用	9.44 MiB
显示代码纯文本
#include <cstdio>
#include <cstdarg>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cctype>
#include <vector>
using namespace std;
#define BETTER_CODE __attribute__((optimize("O3")))
BETTER_CODE
inline int fast_read()
{
    char c;
    int r;
    while(c = getchar())
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return r;
}

#define MAXN 100001
struct node
{
    int l, r, ls, rs;
    int lazyadd;
    int lazyset;
    bool have_lazyset;
    int sum, maxv, minv;
    int maxvcnt, minvcnt;
    BETTER_CODE
    void add(int v)
    {
        lazyadd += v;
        sum += (r-l+1)*v;
        maxv += v;
        minv += v;
    }
    BETTER_CODE
    void set(int v)
    {
        have_lazyset = true;
        lazyset = v;
        lazyadd = 0;  
        sum = (r-l+1)*v;
        minv = maxv = v;
        minvcnt = maxvcnt = r-l+1;
    }
}ns[MAXN<<1];
int last = 1;
#define ld ns[d.ls]
#define rd ns[d.rs]
BETTER_CODE
void pushup(node &d)
{
    d.sum = ld.sum+rd.sum;
    d.maxv = max(ld.maxv, rd.maxv);
    if(ld.maxv > rd.maxv)
        d.maxvcnt = ld.maxvcnt;
    else if(rd.maxv > ld.maxv)
        d.maxvcnt = rd.maxvcnt;
    else d.maxvcnt = ld.maxvcnt + rd.maxvcnt;
    d.minv = min(ld.minv, rd.minv);
    if(ld.minv < rd.minv)
        d.minvcnt = ld.minvcnt;
    else if(rd.minv < ld.minv)
        d.minvcnt = rd.minvcnt;
    else d.minvcnt = ld.minvcnt + rd.minvcnt;
}
BETTER_CODE
int build(int l, int r)
{
    if(l > r)return 0;
    int c = last++;
    node &d = ns[c];
    d.l = l;
    d.r = r;
    if(l == r)
    {
        d.sum = d.minv = d.maxv = fast_read();
        d.minvcnt = d.maxvcnt = 1;
    }else
    {
        int m = (l+r)>>1;
        d.ls = build(l, m);
        d.rs = build(m+1, r);
        pushup(d);
    }
    return c;
}
BETTER_CODE
void pushdown(node &d)
{
    if(d.have_lazyset)
    {
        ld.set(d.lazyset);
        rd.set(d.lazyset);
        d.have_lazyset = false;
    }
    if(d.lazyadd)
    {
        ld.add(d.lazyadd);
        rd.add(d.lazyadd);
        d.lazyadd = 0;
    }
}
BETTER_CODE
int querysum(int c, int l, int r)
{
    if(!c)return 0;
    node &d = ns[c];
    if(d.l == l && d.r == r)
        return d.sum;
    else
    {
        pushdown(d);
        if(r <= ld.r)return querysum(d.ls, l, r);
        else if(l >= rd.l)return querysum(d.rs, l, r);
        else return querysum(d.ls, l, ld.r)+querysum(d.rs, rd.l, r);
    }
}
BETTER_CODE
void setval(int c, int l, int r, int v)
{
    if(!c)return;
    node &d = ns[c];
    if(d.l == l && d.r == r)
    {
        d.set(v);
    }else
    {
        pushdown(d);
        if(r <= ld.r)setval(d.ls, l, r, v);
        else if(l >= rd.l)setval(d.rs, l, r, v);
        else
        {
            setval(d.ls, l, ld.r, v);
            setval(d.rs, rd.l, r, v);
        }
        pushup(d);
    }
}
BETTER_CODE
void addval(int c, int l, int r, int v)
{
    if(!c)return;
    node &d = ns[c];
    if(d.l == l && d.r == r)
    {
        d.add(v);
    }else
    {
        pushdown(d);
        if(r <= ld.r)addval(d.ls, l, r, v);
        else if(l >= rd.l)addval(d.rs, l, r, v);
        else
        {
            addval(d.ls, l, ld.r, v);
            addval(d.rs, rd.l, r, v);
        }
        pushup(d);
    }
}
BETTER_CODE
int querymax(int c, int l, int r)
{
    if(!c)return -0x7fffffff;
    node &d = ns[c];
    if(d.l == l && d.r == r)
        return d.maxv;
    else
    {
        pushdown(d);
        if(r <= ld.r)return querymax(d.ls, l, r);
        else if(l >= rd.l)return querymax(d.rs, l, r);
        else
            return max(querymax(d.ls, l, ld.r), querymax(d.rs, rd.l, r));
    }
}
BETTER_CODE
int querymin(int c, int l, int r)
{
    if(!c)return 0x7fffffff;
    node &d = ns[c];
    if(d.l == l && d.r == r)
        return d.minv;
    else
    {
        pushdown(d);
        if(r <= ld.r)return querymin(d.ls, l, r);
        else if(l >= rd.l)return querymin(d.rs, l, r);
        else
            return min(querymin(d.ls, l, ld.r), querymin(d.rs, rd.l, r));
    }
}
BETTER_CODE
int querymaxc(int c, int l, int r)
{
    if(!c)return 0;
    node &d = ns[c];
    if(d.l == l && d.r == r)
        return d.maxvcnt;
    else
    {
        pushdown(d);
        if(r <= ld.r)querymaxc(d.ls, l, r);
        else if(l >= rd.l)querymaxc(d.rs, l, r);
        else 
        {
            int q1 = querymax(d.ls, l, ld.r);
            int q2 = querymax(d.rs, rd.l, r);
            if(q1 > q2)return querymaxc(d.ls, l, ld.r);
            else if(q1 < q2)return querymaxc(d.rs, rd.l, r);
            else return querymaxc(d.ls, l, ld.r) + querymaxc(d.rs, rd.l, r);
        }
    }
}
BETTER_CODE
int queryminc(int c, int l, int r)
{
    if(!c)return 0;
    node &d = ns[c];
    if(d.l == l && d.r == r)
        return d.minvcnt;
    else
    {
        pushdown(d);
        if(r <= ld.r)queryminc(d.ls, l, r);
        else if(l >= rd.l)queryminc(d.rs, l, r);
        else
        {
            int q1 = querymin(d.ls, l, ld.r);
            int q2 = querymin(d.rs, rd.l, r);
            if(q1 < q2)return queryminc(d.ls, l, ld.r);
            else if(q1 > q2)return queryminc(d.rs, rd.l, r);
            else return queryminc(d.ls, l, ld.r) + queryminc(d.rs, rd.l, r);
        }
    }
}
BETTER_CODE
void setmaxwith(int c, int l, int r, int v)
{
    if(!c)return;
    node &d = ns[c];
    if(d.minv >= v)return;
    if(d.l == l && d.r == r)
    {
       // if(d.minv >= v)return;
        if(d.maxv < v)
            d.set(v);
        else
        {
            pushdown(d);
            setmaxwith(d.ls, ld.l, ld.r, v);
            setmaxwith(d.rs, rd.l, rd.r, v);
            pushup(d);
        }
    }else
    {
        pushdown(d);
        if(r <= ld.r)setmaxwith(d.ls, l, r, v);
        else if(l >= rd.l)setmaxwith(d.rs, l, r, v);
        else
        {
            setmaxwith(d.ls, l, ld.r, v);
            setmaxwith(d.rs, rd.l, r, v);
        }
        pushup(d);
    }
}
BETTER_CODE
void setminwith(int c, int l, int r, int v)
{
    if(!c)return;
    node &d = ns[c];
    if(d.maxv <= v)return;
    if(d.l == l && d.r == r)
    {
        //if(d.maxv <= v)return;
        if(d.minv > v)
            d.set(v);
        else
        {
            pushdown(d);
            setminwith(d.ls, ld.l, ld.r, v);
            setminwith(d.rs, rd.l, rd.r, v);
            pushup(d);
        }
    }else
    {
        pushdown(d);
        if(r <= ld.r)setminwith(d.ls, l, r, v);
        else if(l >= rd.l)setminwith(d.rs, l, r, v);
        else
        {
            setminwith(d.ls, l, ld.r, v);
            setminwith(d.rs, rd.l, r, v);
        }
        pushup(d);
    }
}
char buf[24];
BETTER_CODE
int main()
{
    freopen("redbag.in", "r", stdin);
    freopen("redbag.out", "w", stdout);
    int n = fast_read();
    build(1, n);
    int q = fast_read();
    while(q--)
    {
        char c;
        while(!isalpha(c = getchar()));
        int p = 1;
        buf[0] = c;
        while(isalpha(c = getchar()))buf[p++] = c;
        buf[p] = 0;
        int l = fast_read();
        int r = fast_read();
        if(!strcmp("Cadd", buf))
        {
            int v = fast_read();
            addval(1, l, r, v);
        }else if(!strcmp("Cchange", buf))
        {
            int v = fast_read();
            setval(1, l, r, v);
        }else if(!strcmp("Cbmax", buf))
        {
            int v = fast_read();
            int m = querymax(1, l, r);
            setmaxwith(1, l, r, v);
        }else if(!strcmp("Cbmin", buf))
        {
            int v = fast_read();
            setminwith(1, l, r, v);
        }else if(!strcmp("Qsum", buf))
        {
            printf("%d\n", querysum(1, l, r));
        }else if(!strcmp("Qwmax", buf))
        {
            printf("%d\n", querymax(1, l, r));
        }else if(!strcmp("Qwmin", buf))
            printf("%d\n", querymin(1, l, r));
        else if(!strcmp("Qnmax", buf))
        {
            printf("%d\n", querymaxc(1, l, r));
        }else if(!strcmp("Qnmin", buf))
        {
            printf("%d\n", queryminc(1, l, r));
        }
    }
    return 0;
}