hdu 3911 简单线段树

最新推荐文章于 2019-05-13 21:14:00 发布

HQD因为有趣所以做题

最新推荐文章于 2019-05-13 21:14:00 发布

阅读量808

点赞数

分类专栏： ACM_数据结构文章标签： tree query build include struct

本文链接：https://blog.csdn.net/hqd_acm/article/details/6666555

版权

ACM_数据结构专栏收录该内容

105 篇文章

订阅专栏

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL(x)  (x << 1)
#define RR(x)  (x << 1) | 1
const int MAXN = 100000;
struct Seg_Tree
{
    int l, r;
    bool rev;
    int blmax, brmax, btmax;
    int wlmax, wrmax, wtmax;
    int mid()  {return (l + r) >> 1;}
}tree[MAXN * 3];
void update_info(int idx)
{
    int mid = tree[idx].mid();
    int len1 = mid - tree[idx].l + 1;
    int len2 = tree[idx].r - mid;
    if(tree[LL(idx)].blmax == len1)  tree[idx].blmax = len1 + tree[RR(idx)].blmax;
    else tree[idx].blmax = tree[LL(idx)].blmax;
    if(tree[RR(idx)].brmax == len2)  tree[idx].brmax = len2 + tree[LL(idx)].brmax;
    else tree[idx].brmax = tree[RR(idx)].brmax;
    tree[idx].btmax = max(tree[LL(idx)].brmax + tree[RR(idx)].blmax,
                                         max(tree[LL(idx)].btmax, tree[RR(idx)].btmax));

    if(tree[LL(idx)].wlmax == len1)  tree[idx].wlmax = len1 + tree[RR(idx)].wlmax;
    else tree[idx].wlmax = tree[LL(idx)].wlmax;
    if(tree[RR(idx)].wrmax == len2)   tree[idx].wrmax = len2 + tree[LL(idx)].wrmax;
    else tree[idx].wrmax = tree[RR(idx)].wrmax;
    tree[idx].wtmax = max(tree[LL(idx)].wrmax + tree[RR(idx)].wlmax,
                                         max(tree[LL(idx)].wtmax, tree[RR(idx)].wtmax));
}
void change(int idx)
{
    swap(tree[idx].wlmax, tree[idx].blmax);
    swap(tree[idx].wrmax, tree[idx].brmax);
    swap(tree[idx].wtmax, tree[idx].btmax);
}
void push_down(int idx)
{
    change(LL(idx));
    change(RR(idx));
    tree[LL(idx)].rev ^= 1;
    tree[RR(idx)].rev ^= 1;
    tree[idx].rev = 0;
}
void build(int l, int r, int idx)
{
    tree[idx].l = l;
    tree[idx].r = r;
    tree[idx].rev = 0;
    if(l == r)
    {
        int x;
        scanf("%d", &x);
        if(x)
        {
            tree[idx].blmax = tree[idx].brmax = tree[idx].btmax = 1;
            tree[idx].wlmax = tree[idx].wrmax = tree[idx].wtmax = 0;
        }
        else
        {
            tree[idx].blmax = tree[idx].brmax = tree[idx].btmax = 0;
            tree[idx].wlmax = tree[idx].wrmax = tree[idx].wtmax = 1;
        }
        return;
    }
    int mid = tree[idx].mid();
    build(l, mid, LL(idx));
    build(mid + 1, r, RR(idx));
    update_info(idx);
}
void update(int l ,int r, int idx)
{
    if(l <= tree[idx].l && tree[idx].r <= r)
    {
        change(idx);
        tree[idx].rev ^= 1;
        return;
    }

    if(tree[idx].rev)  push_down(idx);

    int mid = tree[idx].mid();
    if(mid >= l)  update(l, r, LL(idx));
    if(r > mid)  update(l, r, RR(idx));
    update_info(idx);
}
int query(int l, int r, int idx)
{
    if(l <= tree[idx].l && tree[idx].r <= r)
    {
        return tree[idx].btmax;
    }
    if(tree[idx].rev)  push_down(idx);

    int mid = tree[idx].mid();
    int a, b;
    if(mid < l) return query(l, r, RR(idx));
    else if(mid >= r)  return query(l, r, LL(idx));
    else
    {
        a = query(l, mid, LL(idx));
        b = query(mid+1, r, RR(idx));
        a = max(a, b);
        b = min(tree[LL(idx)].brmax, mid - l + 1) + min(tree[RR(idx)].blmax, r - mid);
        return max(a, b);
    }
}
int main()
{
    int n,m;
    while(scanf("%d", &n) != EOF)
    {
        build(1, n, 1);
        scanf("%d", &m);
        int x, y, z;
        while(m--)
        {
            scanf("%d%d%d", &x, &y, &z);
            if(x == 1)
            {
                update(y, z, 1);
            }
            else
            {
                printf("%d\n",query(y, z, 1));
            }
        }
    }
    return 0;
}