hdu 3397

最新推荐文章于 2019-05-03 21:34:27 发布

原创最新推荐文章于 2019-05-03 21:34:27 发布 · 1.3k 阅读

0 ·

CC 4.0 BY-SA版权

文章标签：

#tree #query #build #struct

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 Struct_tree
{
    int l, r, len;
    int color;
    int sum;
    int lmax, rmax, tmax;//1的长度
    int mid()
    {
        return (l + r) >> 1;
    }
} tree[MAXN * 3];

int num[MAXN];

void update_info(int idx)
{
    if(tree[LL(idx)].color == tree[RR(idx)].color)  tree[idx].color = tree[LL(idx)].color;
    else tree[idx].color = -1;

    if(tree[idx].color == 1)
    {
        tree[idx].sum = tree[idx].lmax = tree[idx].rmax = tree[idx].tmax = tree[idx].len;
    }
    else if(tree[idx].color == 0)
    {
        tree[idx].sum = tree[idx].lmax = tree[idx].rmax = tree[idx].tmax = 0;
    }
    else
    {
        tree[idx].sum = tree[LL(idx)].sum + tree[RR(idx)].sum;

        if(tree[LL(idx)].lmax == tree[LL(idx)].len)  tree[idx].lmax = tree[LL(idx)].lmax + tree[RR(idx)].lmax;
        else tree[idx].lmax = tree[LL(idx)].lmax;
        if(tree[RR(idx)].rmax == tree[RR(idx)].len)  tree[idx].rmax = tree[LL(idx)].rmax + tree[RR(idx)].rmax;
        else tree[idx].rmax = tree[RR(idx)].rmax;

        tree[idx].tmax = max(tree[LL(idx)].rmax + tree[RR(idx)].lmax,
                                       max(tree[LL(idx)].tmax, tree[RR(idx)].tmax));
    }
}

void build(int l, int r, int idx)
{
    tree[idx].l = l;
    tree[idx].r = r;
    tree[idx].len = r - l + 1;
    if(l == r)
    {
        tree[idx].lmax = tree[idx].rmax = tree[idx].tmax = tree[idx].sum = tree[idx].color = num[l];
        return;
    }
    int mid = tree[idx].mid();
    build(l, mid, LL(idx));
    build(mid+1, r, RR(idx));
    update_info(idx);
}

void push_down(int idx)
{
    tree[LL(idx)].color = tree[RR(idx)].color = tree[idx].color;
    if(tree[idx].color == 1)
    {
        tree[LL(idx)].sum = tree[LL(idx)].lmax = tree[LL(idx)].rmax = tree[LL(idx)].tmax = tree[LL(idx)].len;
        tree[RR(idx)].sum = tree[RR(idx)].lmax = tree[RR(idx)].rmax = tree[RR(idx)].tmax = tree[RR(idx)].len;
    }
    else
    {
        tree[LL(idx)].sum = tree[LL(idx)].lmax = tree[LL(idx)].rmax = tree[LL(idx)].tmax = 0;
        tree[RR(idx)].sum = tree[RR(idx)].lmax = tree[RR(idx)].rmax = tree[RR(idx)].tmax = 0;
    }
    tree[idx].color = -1;
}

void update(int l, int r, int k, int idx)
{
    if(tree[idx].color == k)  return; //没必要下去了

    if(l <= tree[idx].l && tree[idx].r <= r)
    {
        tree[idx].color = k;
        if(k == 0)  tree[idx].sum = tree[idx].lmax = tree[idx].rmax = tree[idx].tmax = 0;
        else tree[idx].sum = tree[idx].lmax = tree[idx].rmax = tree[idx].tmax = tree[idx].len;
        return;
    }

    if(tree[idx].color != -1)  push_down(idx);

    int mid = tree[idx].mid();
    if(mid >= l)  update(l, r, k, LL(idx));
    if(mid < r) update(l, r, k, RR(idx));
    update_info(idx);
}

void update_xor(int l, int r, int idx)
{
    if(l <= tree[idx].l && tree[idx].r <= r && tree[idx].color != -1)
    {
        if(tree[idx].color == 1) tree[idx].sum = tree[idx].lmax = tree[idx].rmax = tree[idx].tmax = 0;
        else tree[idx].sum = tree[idx].lmax = tree[idx].rmax = tree[idx].tmax = tree[idx].len;
        tree[idx].color ^= 1;
        return;
    }

    if(tree[idx].color != -1)  push_down(idx);

    int mid = tree[idx].mid();
    if(mid >= l)  update_xor(l, r, LL(idx));
    if(mid < r) update_xor(l, r, RR(idx));
    update_info(idx);
}

int Query(int l, int r, int idx)
{
    if(tree[idx].color == 0)  return 0;
    if(tree[idx].color == 1)  return r - l + 1;
    if(l <= tree[idx].l && tree[idx].r <= r)  return tree[idx].sum;
    //肯定没有没有标记下传的情况，因为标记下传的话，在三面三句话里都已经返回了
    int mid = tree[idx].mid();
    if(mid < l)  return Query(l, r, RR(idx));
    else if(mid >= r) return Query(l, r, LL(idx));
    else return Query(l, mid, LL(idx)) + Query(mid+1, r, RR(idx));
}

int Query_slen(int l, int r, int idx)
{
    if(tree[idx].color == 0)  return 0;
    if(tree[idx].color == 1)
    {
        return r - l + 1;
    }
    if(l <= tree[idx].l && tree[idx].r <= r)  return tree[idx].tmax;
    int mid = tree[idx].mid();
    if(mid < l)  return Query_slen(l, r, RR(idx));
    else if(mid >= r) return Query_slen(l, r, LL(idx));
    else
    {
        int len1 = Query_slen(l, mid, LL(idx));
        int len2 = Query_slen(mid+1, r, RR(idx));
        int len0 = min(tree[LL(idx)].rmax, mid - l + 1) + min(tree[RR(idx)].lmax, r - mid);
        return max(len0, max(len1, len2));
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    int op, a, b, n, m;
    while(T--)
    {
        scanf("%d%d",&n,&m);

        for(int i=1; i<=n; i++)  scanf("%d", &num[i]);

        build(1, n, 1);

        while(m--)
        {
            scanf("%d%d%d", &op, &a, &b);
            a++;
            b++;
            switch(op)
            {
            case 0:
                update(a,b,0,1);
                break;
            case 1:
                update(a,b,1,1);
                break;
            case 2:
                update_xor(a,b,1);
                break;
            case 3:
                printf("%d\n",Query(a,b,1));
                break;
            case 4:
                printf("%d\n",Query_slen(a,b,1));
            }
        }
    }
    return 0;
}