BZOJ4695: 最假女选手
线段树 工业 技巧    2016-12-06 20:03:57    357    0    0
jszyxw   线段树 工业 技巧

4695: 最假女选手

Time Limit: 50 Sec  Memory Limit: 128 MB
Submit: 111  Solved: 17
[Submit][Status][Discuss]

Description

在刚刚结束的水题嘉年华的压轴节目放水大赛中,wyywyy如愿以偿的得到了最假女选手的奖项。但是作为主办人的
C_SUNSHINE为了证明wyywyy确实在放水,决定出一道基础题考察wyywyy的姿势水平。给定一个长度为 N序列,编号
从1 到 N。要求支持下面几种操作:
1.给一个区间[L,R] 加上一个数x 
2.把一个区间[L,R] 里小于x 的数变成x 
3.把一个区间[L,R] 里大于x 的数变成x 
4.求区间[L,R] 的和
5.求区间[L,R] 的最大值
6.求区间[L,R] 的最小值

 

Input

第一行一个整数 N表示序列长度。
第二行N 个整数Ai 表示初始序列。
第三行一个整数M 表示操作个数。
接下来M 行,每行三或四个整数,第一个整数Tp 表示操作类型,接下来L,R,X 或L,R 表述操作数。
1<=tp<=6,N,M<=5*10^5,|Ai|<=10^8
Tp=1时,|x|<=1000
Tp=2或3时,|x|<=10^8

 

Output

对于每个4,5,6类型的操作输出一行一个整数表示答案。

 

Sample Input

2
1 2
2
2 1 2 2
4 1 2

Sample Output

4

Solution

辣鸡工业题

吉如一的paper上有详细的题解与证明

细节比较多,写之前一定要想清楚。。

不然会像我一样调两个晚上QAQ


Source code

#include <bits/stdc++.h>
 
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
 
template <class T> inline void chkmin(T &x, T y) { x > y && (x = y); }
template <class T> inline void chkmax(T &x, T y) { x < y && (x = y); }
 
template <class T> inline T &read(T &x)
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) {
        if (c == '-')
            f = -1;
    }
    for (x = 0; isdigit(c); c = getchar()) {
        x = x * 10 + c - 48;
    }
    return x *= f;
}
 
template <class T> inline void write(T x, const char p = '\n')
{
    static int top;
    static int s[30];
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    do s[++ top] = x % 10 + 48;
    while (x /= 10);
    while (top)
        putchar(s[top --]);
    putchar(p);
}
 
const int maxn = 5e5 + 5;
const int oo = 0x3f3f3f3f;
 
int n, m;
 
namespace Segment
{
    long long s[maxn << 2];
 
    int mx[maxn << 2];
    int mn[maxn << 2];
    int mx2[maxn << 2];
    int mn2[maxn << 2];
    int mxnum[maxn << 2];
    int mnnum[maxn << 2];
 
    int add[maxn << 2];
    int size[maxn << 2];
 
#define LS (x << 1)
#define RS (x << 1 | 1)
 
    inline void Add(int &x, int y) { if (x - oo && x + oo) x += y; }
 
    inline void workmin(int x, int v)
    {
        if (mx[x] <= v || v <= mx2[x]) return;
        s[x] -= (long long)mxnum[x] * (mx[x] - v);
        mx[x] = v;
        chkmin(mn[x], v);
        if (mx[x] == mn[x]) {
            mxnum[x] = mnnum[x] = size[x];
            s[x] = (long long)size[x] * mx[x];
            mx2[x] = -oo;
            mn2[x] = oo;
        } else
            chkmin(mn2[x], v);
    }
 
    inline void workmax(int x, int v)
    {
        if (mn[x] >= v || v >= mn2[x]) return;
        s[x] += (long long)mnnum[x] * (v - mn[x]);
        mn[x] = v;
        chkmax(mx[x], v);
        if (mx[x] == mn[x]) {
            mxnum[x] = mnnum[x] = size[x];
            s[x] = (long long)mx[x] * size[x];
            mx2[x] = -oo;
            mn2[x] = oo;
        } else
            chkmax(mx2[x], v);
    }
 
    inline void pushup(int x)
    {
        s[x] = s[LS] + s[RS];
        if (mx[LS] == mx[RS]) {
            mx[x] = mx[LS];
            mxnum[x] = mxnum[LS] + mxnum[RS];
            mx2[x] = std::max(mx2[LS], mx2[RS]);
        } else if (mx[LS] < mx[RS]) {
            mx[x] = mx[RS];
            mxnum[x] = mxnum[RS];
            mx2[x] = std::max(mx2[RS], mx[LS]);
        } else {
            mx[x] = mx[LS];
            mxnum[x] = mxnum[LS];
            mx2[x] = std::max(mx2[LS], mx[RS]);
        }
        if (mn[LS] == mn[RS]) {
            mn[x] = mn[LS];
            mnnum[x] = mnnum[LS] + mnnum[RS];
            mn2[x] = std::min(mn2[LS], mn2[RS]);
        } else if (mn[LS] > mn[RS]) {
            mn[x] = mn[RS];
            mnnum[x] = mnnum[RS];
            mn2[x] = std::min(mn2[RS], mn[LS]);
        } else {
            mn[x] = mn[LS];
            mnnum[x] = mnnum[LS];
            mn2[x] = std::min(mn2[LS], mn[RS]);
        }
    }
 
    inline void pushdown(int x)
    {
        if (add[x]) {
            add[LS] += add[x];
            add[RS] += add[x];
            mn[LS] += add[x];
            mn[RS] += add[x];
            Add(mn2[LS], add[x]);
            Add(mn2[RS], add[x]);
            mx[LS] += add[x];
            mx[RS] += add[x];
            Add(mx2[LS], add[x]);
            Add(mx2[RS], add[x]);
            s[LS] += (long long)size[LS] * add[x];
            s[RS] += (long long)size[RS] * add[x];
            add[x] = 0;
        }
        workmax(LS, mn[x]);
        workmin(LS, mx[x]);
        workmax(RS, mn[x]);
        workmin(RS, mx[x]);
    }
 
    void build(int x, int l, int r)
    {
        if (l == r) {
            size[x] = 1;
            mn[x] = mx[x] = read(s[x]); 
            mx2[x] = -oo;
            mn2[x] = oo;
            mxnum[x] = mnnum[x] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(LS, l, mid);
        build(RS, mid + 1, r);
        pushup(x);
        size[x] = size[LS] + size[RS];
    }
 
    void update_add(int x, int l, int r, int p, int q, int v)
    {
        if (l != r) pushdown(x);
        if (p <= l && r <= q) {
            add[x] += v;
            mn[x] += v;
            mx[x] += v;
            Add(mx2[x], v);
            Add(mn2[x], v);
            s[x] += (long long)size[x] * v;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update_add(LS, l, mid, p, q, v);
        if (q > mid) update_add(RS, mid + 1, r, p, q, v);
        pushup(x);
    }
 
    void update_min(int x, int l, int r, int p, int q, int v)
    {
        if (mx[x] <= v) return;
        if (p <= l && r <= q && mx2[x] < v) {
            workmin(x, v);
            return;
        }
        pushdown(x);
        int mid = (l + r) >> 1;
        if (p <= mid) update_min(LS, l, mid, p, q, v);
        if (q > mid) update_min(RS, mid + 1, r, p, q, v);
        pushup(x);
    }
 
    void update_max(int x, int l, int r, int p, int q, int v)
    {
        if (mn[x] >= v) return;
        if (p <= l && r <= q && mn2[x] > v) {
            workmax(x, v);
            return;
        }
        pushdown(x);
        int mid = (l + r) >> 1;
        if (p <= mid) update_max(LS, l, mid, p, q, v);
        if (q > mid) update_max(RS, mid + 1, r, p, q, v);
        pushup(x);
    }
 
    int p, q;
    int ret;
    long long Ret;
 
    void query_sum(int x, int l, int r)
    {
        if (p <= l && r <= q) {
            Ret += s[x];
            return;
        }
        pushdown(x);
        int mid = (l + r) >> 1;
        if (p <= mid) query_sum(LS, l, mid);
        if (q > mid) query_sum(RS, mid + 1, r);
    }
 
    void query_max(int x, int l, int r)
    {
        if (p <= l && r <= q) {
            chkmax(ret, mx[x]);
            return;
        }
        pushdown(x);
        int mid = (l + r) >> 1;
        if (p <= mid) query_max(LS, l, mid);
        if (q > mid) query_max(RS, mid + 1, r);
    }
 
    void query_min(int x, int l, int r)
    {
        if (p <= l && r <= q) {
            chkmin(ret, mn[x]);
            return;
        }
        pushdown(x);
        int mid = (l + r) >> 1;
        if (p <= mid) query_min(LS, l, mid);
        if (q > mid) query_min(RS, mid + 1, r);
    }
 
    inline void Query_min(int L, int R)
    {
        ret = oo;
        p = L, q = R;
        query_min(1, 1, n);
        write(ret);
    }
 
    inline void Query_max(int L, int R)
    {
        ret = -oo;
        p = L, q = R;
        query_max(1, 1, n);
        write(ret);
    }
 
    inline void Query_sum(int L, int R)
    {
        Ret = 0;
        p = L, q = R;
        query_sum(1, 1, n);
        write(Ret);
    }
}
 
int main() 
{
    if (fopen("4695.in", "r") != NULL) {
        freopen("4695.in", "r", stdin);
        freopen("4695.out", "w", stdout);
    }
 
    static int opt, x, y, v;
 
    for (Segment::build(1, 1, read(n)), read(m); m --; ) {
        read(opt);
        read(x), read(y);
        if (opt == 1)
            Segment::update_add(1, 1, n, x, y, read(v));
        else if (opt == 2)
            Segment::update_max(1, 1, n, x, y, read(v));
        else if (opt == 3)
            Segment::update_min(1, 1, n, x, y, read(v));
        else if (opt == 4)
            Segment::Query_sum(x, y);
        else if (opt == 5)
            Segment::Query_max(x, y);
        else if (opt == 6)
            Segment::Query_min(x, y);
    }
 
    return 0;
}


在win10下使用linux软件
357 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航