泡椒凤爪树

240_F_156035441_pkTsRAyS7VijOt9JKlbMkzjjRZvRUVc9

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<map>
#include<string>
using namespace std;
const int maxn = 1000000 + 10;
string str[100];
const int INF = 2000000000;
int q, x1_, x2_, y1, y2, v_add, v_set,v_bri;

struct segment_tree
{
    int sumv[4*maxn],minv[4*maxn],maxv[4*maxn];
    int addv[4*maxn], setv[4*maxn];

    void maintain(int o,int L,int R)
    {
        int lc = o*3-1,mc = o*3,rc = o*3+1;
        sumv[o] = minv[o] = maxv[o] = 0;
        if(setv[o] >= 0)
        {
            sumv[o] = setv[o] * (R-L+1);
            minv[o] = maxv[o] =setv[o];
        }
        else if(R > L)
        {
            sumv[o] = sumv[lc]+sumv[mc]+sumv[rc];
            minv[o] = min(minv[lc],min(minv[mc],minv[rc]));
            maxv[o] = max(maxv[lc],max(maxv[mc],maxv[rc]));
        }
        minv[o] += addv[o];
        maxv[o] += addv[o];
        sumv[o] += addv[o] * (R-L+1);
    }

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

    void update_add(int o,int L,int R)
    {
        int lc = o*3-1,mc = o*3,rc = o*3+1;
        printf("现在进入节点%d,他的左边是%d,右边是%d\n",o,L,R);
        if(y1 <= L && y2 >= R)
        {
            addv[o] += v_add;
            printf("节点%d的价值为%d\n",o,addv[o]);
        }
        else
        {
            pushdown(o);

            int ll = L + (R - L + 1)/3 - 1,rr = L + (R - L + 1)/3*2 - 1;
            printf("左三点为%d,右三点为%d\n",ll,rr);

            if(y1 <= ll)                 update_add(o*3-1,L,ll);             else                 maintain(o*3-1,L,ll);             if(((y2 > rr)&&(y1 <= rr)) || ((y2 >ll)&&(y1 <= ll)))                 update_add(o*3,ll+1,rr);             else                 maintain(o*3,ll+1,rr);             if(y2 > rr)
                update_add(o*3+1,rr+1,R);
            else
                maintain(o*3+1,rr+1,R);

        }
        maintain(o,L,R);
    }

    void update_set(int o,int L,int R)
    {
         printf("现在进入节点%d,他的左边是%d,右边是%d\n",o,L,R);
        int lc = 3*o-1,mc = 3*o,rc = o*3+1;
        if(y1 <= L&&y2 >= R)
        {
            setv[o] = v_set;
            addv[o] = 0;
             printf("节点%d的修改设置为%d\n",o,setv[o]);
        }
        else
        {
            pushdown(o);
            int ll = L + (R - L + 1)/3 - 1,rr = L + (R - L + 1)/3*2 - 1;
            printf("左三点为%d,右三点为%d\n",ll,rr);

            if(y1 <= ll)                 update_set(o*3-1,L,ll);             else                 maintain(o*3-1,L,ll);             if(((y2 > rr)&&(y1 <= rr)) || ((y2 >ll)&&(y1 <= ll)))                 update_set(o*3,ll+1,rr);             else                 maintain(o*3,ll+1,rr);             if(y2 > rr)
                update_set(o*3+1,rr+1,R);
            else
                maintain(o*3+1,rr+1,R);
        }
    }
    void query(int o,int L,int R,int add,int& _min,int& _sum,int& _max)
    {
        printf("询问进入节点%d,他的左边是%d,右边是%d\n",o,L,R);
        if(setv[o] >= 0)
        {
            _sum += (add+setv[o] + addv[o])*(min(R,y2) - max(L,y1)+1);
            _min = min(_min,setv[o] + addv[o] +add);
            _max = max(_max,setv[o] + addv[o] +add);
        }
        else if(y1 <= L && y2 >= R)
        {
            _sum += sumv[o] + add*(R - L + 1);
            _min = min(_min,minv[o] + add);
            _max = max(_max,maxv[o] + add);
            printf("全部包括!\n");
        }
        else
        {
            int ll = L + (R - L + 1)/3 - 1,rr = L + (R - L + 1)/3*2 - 1;
            printf("左三点为%d,右三点为%d\n",ll,rr);
            if(y1 <= ll)                 query(o*3-1,L,ll,add + addv[o],_min,_sum,_max);             if(((y2 > rr)&&(y1 <= rr)) || ((y2 >ll)&&(y1 <= ll)))                 query(o*3,ll+1,rr,add+addv[o],_min,_sum,_max);             if(y2 > rr)
                query(o*3+1,rr+1,R,add+addv[o],_min,_sum,_max);

        }

    }

    void init()
    {
        memset(setv, -1, sizeof(setv));
        memset(addv, 0, sizeof(addv));
        memset(sumv, 0, sizeof(sumv));
        memset(minv, 0, sizeof(minv));
        memset(maxv, 0, sizeof(maxv));
    }
};
int r, c, m;
const int maxr = 20 + 5;

segment_tree tree;

int main()
{

    scanf("%d%d",&c, &m);
    {

        tree.init();
        int x = 1;
        while(c > x)
            x*=3;
        c=x;
        for(int i = 0; i < m; i++)
        {

            scanf("%d%d%d", &q,&y1,&y2);
            if(q == 1)
            {
                scanf("%d", &v_add);

                tree.update_add(1, 1, c);

            }
            if(q == 2)
            {
                scanf("%d", &v_set);

                tree.update_set(1, 1, c);

            }
            if(q == 3)
            {

                int _min = INF, _max = -INF, _sum = 0;
                tree.query(1, 1, c, 0,_min, _sum, _max);
                printf("%d %d %d\n", _sum, _min, _max);
            }

        }
    }
    return 0;
}

其实就是线段树加三分搜索。
线段树一个父节点只有左右两儿子,好,那么我根据仿生学的精神,参照鸡爪的样子,让父节点有了三个爪牙。

父节点的左爪子就是o*3-1,中爪子是o*3,右爪子是o*3+1。支持大面积虱子繁殖,虱子定居,虱子查询。

于是好吃的泡椒凤爪树就出炉啦!
虽然泡椒凤爪树既不漂亮也不实用,但是,它一定会像丑小鸭一样,终有一天,要变成
餐桌上的一道美味。
话说我还想把舞蹈链改成3D舞蹈链,工程有点浩大啊…

Leave a Reply