HDU 3397 Sequence operation

2010-05-03  来源:本站原创  分类:CPP  人气:225 

This question has done quite feeling ... as if the tree line is always flexible, but I think it should also be the rule-based allocation of gvim to write their own, feeling pretty good this time also learned a little bit tricky is infinite WA violence can write a program on the beat, This question is though can not step by step for tracking data, but this is still on the beat inspired me a lot

Segment tree cover should be recorded that the current node to overwrite, and then the type of coverage or Trilogy: distribution of information before entering the child nodes, recursively call the child node, merging information from a child node to return

/*
 * Author: rush
 * Created Time:  2010 Last  01 Day Saturday   15 Seventeen  10 Seconds
 * File Name: icpc/hdu/3397.cpp
 */
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using std::swap;
using std::max;

int max3(int a, int b, int c)
{ return max(a, max(b, c)); }
int max4(int a, int b, int c, int d)
{ return max(a, max3(b, c, d)); }

const int size = 100000 + 5;
struct node_t {
        int L0, M0, R0;
        int L1, M1, R1;
        int ONE;
        int range;
        int cover; //  The coverage  (-1 Is not covered, 0, 1, 2 as  )
        void reset(const int _r)
        {
                range = _r;
                L0 = M0 = R0 = range;
                L1 = M1 = R1 = 0;
                ONE = 0;
        }
        void perform(int op)
        {
                switch (op) {
                case 0:
                        L0 = M0 = R0 = range;
                        L1 = M1 = R1 = 0;
                        ONE = 0;
                        cover = 0;
                        break;
                case 1:
                        L0 = M0 = R0 = 0;
                        L1 = M1 = R1 = range;
                        ONE = range;
                        cover = 1;
                        break;
                case 2:
                        swap(L0, L1), swap(M0, M1), swap(R0, R1);
                        ONE = range - ONE;
                        //  Here is the key, according to the coverage of prior to determine the coverage of now  ,
                        //  In fact, for case 0 and  case 1 Also has this problem, but because it is directly alter the final value is  0 Or  1,
                        //  As opposed to case 2 such changes according to the situation before  , So there is no such points processing
                        switch (cover) {
                        case -1:
                                cover = 2; break;
                        case 0:
                                cover = 1; break;
                        case 1:
                                cover = 0; break;
                        case 2:
                                cover = -1; break;
                        }
                        break;
                }
        }
} tree[size * 3];
int n, m;

void plant(int low, int high, int node)
{
        tree[node].reset(high - low + 1);
        tree[node].cover = -1;
        int mid = (low + high) / 2;
        // low < high  Just to be able to handle  [x, x] The interval  ( That is, for a single point of interval  )
        if (low < high)
        {
                plant(low, mid, node * 2);
                plant(mid + 1, high, node * 2 + 1);
        }
}

int left, right;
void update(int low, int high, int node, int op)
{
        if (left <= low && high <= right) {
                tree[node].perform(op);
        } else if (left <= high && low <= right) {
                int mid = (low + high) / 2;
                //  Before entering the recursive, if the current node to be overwritten  , It is passed to the child node
                if (tree[node].cover != -1)
                {
                        tree[node * 2].perform(tree[node].cover);
                        tree[node * 2 + 1].perform(tree[node].cover);
                        tree[node].cover = -1;
                }
                //  Recursive calls around the child nodes, do not judge here  low < high Because if there is a single-point interval  ,
                //  The point is this function of the first if taking into account the
                update(low, mid, node * 2, op);
                update(mid + 1, high, node * 2 + 1, op);
                //  The child nodes from the left and right back, update parent node information
                node_t &pnt = tree[node], &lch = tree[node * 2], &rch = tree[node * 2 + 1];
                pnt.L0 = lch.L0 + (lch.L0 == lch.range ? rch.L0 : 0);
                pnt.M0 = max3(lch.M0, lch.R0 + rch.L0, rch.M0);
                pnt.R0 = rch.R0 + (rch.R0 == rch.range ? lch.R0 : 0);

                pnt.L1 = lch.L1 + (lch.L1 == lch.range ? rch.L1 : 0);
                pnt.M1 = max3(lch.M1, lch.R1 + rch.L1, rch.M1);
                pnt.R1 = rch.R1 + (rch.R1 == rch.range ? lch.R1 : 0);

                pnt.ONE = lch.ONE + rch.ONE;
        }
}
//  In fact, only need to record the interval was asked into which  2 * log n Subinterval.  ,
//  So it is not normal practice, but like me they're marked the same is true of the
int a[32 * 2], la;
void query(int low, int high, int node)
{
        if (left <= low && high <= right) {
                a[la++] = node;
        } else if (left <= high && low <= right) {
                int mid = (low + high) / 2;
                //  The query is also required when the parent node information passed to the child node  ,
                //  This is because the previous update function can only be guaranteed from  2*logn Subinterval to information is correct
                //  The update does not do  ( If you have done is to index the complexity of the  )
                if (tree[node].cover != -1)
                {
                        tree[node * 2].perform(tree[node].cover);
                        tree[node * 2 + 1].perform(tree[node].cover);
                        tree[node].cover = -1;
                }
                query(low, mid, node * 2);
                query(mid + 1, high, node * 2 + 1);
        }
}

int main()
{
        freopen("data.in", "r", stdin);
        freopen("my.out", "w", stdout);
        int T;
        scanf("%d", &T);
        while (T--)
        {
                scanf("%d%d", &n, &m);
                plant(0, n - 1, 1);
                int t;
                for (int i = 0; i < n; ++i)
                {
                        scanf("%d", &t);
                        left = right = i;
                        update(0, n - 1, 1, t);
                }
                for (int i = 0; i < m; ++i)
                {
                        scanf("%d%d%d", &t, &left, &right);
                        if (t < 3) {
                                update(0, n - 1, 1, t);
                        } else {
                                la = 0;
                                query(0, n - 1, 1);
                                if (t == 3) {
                                        int ans3 = 0;
                                        for (int j = 0; j < la; ++j)
                                                ans3 += tree[a[j]].ONE;
                                        printf("%d\n", ans3);
                                } else {
                                        int ans4 = 0;
                                        for (int j = 0; j < la; ++j)
                                                ans4 = max(ans4, tree[a[j]].M1);
                                        int tmp = 0;
                                        for (int j = 0; j < la; ++j)
                                                if (tree[a[j]].ONE == tree[a[j]].range) {
                                                        tmp += tree[a[j]].range;
                                                } else {
                                                        tmp += tree[a[j]].L1;
                                                        ans4 = max(ans4, tmp);
                                                        tmp = tree[a[j]].R1;
                                                }
                                        ans4 = max(ans4, tmp);
                                        printf("%d\n", ans4);
                                }
                        }
                }
        }
    return 0;
}
相关文章
  • HDU 3397 Sequence operation 2010-05-03

    This question has done quite feeling ... as if the tree line is always flexible, but I think it should also be the rule-based allocation of gvim to write their own, feeling pretty good this time also learned a little bit tricky is infinite WA violenc

  • [HDU] [3397] [Sequence operation] [segment tree] 2010-05-01

    This question has written a cup with the afternoon was so ordered. . #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> using namespace std; int const N= 100010; int n, m; struct Node{ int Lx1, Rx1, Ax1;

  • Summary of python learning 2010-06-20

    python has a very rich data types, Including strings, lists, tuples, dictionaries and other collections, the characteristics of each data type are large, like, make the best use they can make your python program become very easy to make good use of t

  • freemarker getting started manual 2010-11-02

    freemarker official document http://freemarker.sourceforge.net/docs/index.html (1) template + = output FreeMarker data model designers and programmers are based on different professional skills of different individuals of the concept of division of l

  • ETL tasks using the kettle design some 2011-04-02

    Abstract: This paper introduces a number of ETL tasks using the kettle when designing some of the common problems that most are not in the official FAQ, you can find in the kettle of the forum answers questions 1. Join I got A data stream (either fil

  • (Reprinted) one-time encryption and pseudo-random bit sequence 2008-06-09

    In this chapter we introduce a simple specialized machine called a linear feedback shift register (LFSR). We describe how it works, discover interesting applications, and study its limitations. Later, in the book, we will repeat the same process with

  • Flex Array Operation 2010-03-08

    Array provides a variety of methods insert and delete elements. Through these methods, you can quickly according to need to operate Array elements. Array class provides a pair of methods push and pop methods, makes the Array class implements the stac

  • Clojure: Fibonacci sequence problem 2010-03-24

    What is Clojure? Is a new language? Trouble is not Fana? This is the first language is not enough you with? Yes, each language is generally a little thing, but to so something special from time to learn the full reason. However, Clojure is really qui

  • Oracle sequence in Hibernate since the increase in the allocation method 2010-02-18

    In many cases, we use Hibernate in the database has been established on the basis of good. In oracle, if well-established use of the database sequence, you can follow the following steps to get it into Hibernate in: 1, first create a sequence in orac

  • perl-list and array. basic operation. qw. scalar 2010-03-07

    1, List is included in brackets the value of a sequence, can be any value can be empty, such as: (1, 5.3, "hello", 2), an empty list: (). Note: The list contains only a numeric value (such as: (43.2)) and the value itself (ie: 43.2) is different

  • oracle note 4 (common operation) 2010-03-05

    Transaction show ends the transaction: commit / rollback (rollback roll back to default, the first transaction side) Implicitly commits the transaction: DDL / DCL Save Points: savepoint (submitted after the save point release) Savepoint A; Rollback t

  • Sequence "of-order number" of the solving (more superior algorithm) 2010-04-09

    Topics discussed: Quote Two sequences by the same letter, only two sequences of different order "out of order" refers to any sequence in a select two elements to see whether the sequence in another sequence, the question is how different the num

  • [Change] UML in the data flow diagram, use case diagram, class diagram, object diagram, role diagram, activity diagram, sequence diagram for detailed information about preservation 2010-04-26

    * One-way association In a one-way association, two classes are related, but only one class to know the existence of such links. A one-way association, expressed as an open class with the arrow pointing to the known (not shut down arrow or triangle,

  • python notes sequence 2010-05-04

    Well, to make their own projects with the shortest time possible to achieve some of the features, but also picked up the python ..... Sequence: an ordered set of data collection (because all can be ordered to repeat), Sequence can be divided into two

  • ORACLE Sequence from growth 2010-05-13

    Sequence is a database system according to certain rules automatically increase the number of sequences. This sequence usually the primary key as the agent (because it would not repeat), no other meaning. Sequence characteristics of the database syst

  • JavaScript journey Study Notes (8) operation DOM Document (1) 2010-05-30

    The entire document is composed of a collection of many nodes, the node refers to elements in the document and the elements contained in the text. These nodes can have different node types. Each node in the document tree object has a nodeType propert

  • Jbpm4 common operation 2010-06-10

    1, process definition 1. To deploy process definition ProcessEngine processEngine = new Configuration (). BuildProcessEngine (); RepositoryService repositoryService = processEngine.getRepositoryService (); Example: the process of deploying file / / D

  • flex examples of program execution sequence 2010-06-19

    Core Description: 1, view of a flex system program execution sequence: 1. Global variable region; 2. External custom component area; 3. Four keywords (preinitialize / initialize / creationComplete / applicationComplete). 2, defines a class of referen

  • MapReduce MapReduce operation based on data flow optimization 2010-06-22

    In the preparation of MapReduce applications, in addition to the basic Map module, Reduce module and driving method, the user can also optimizing operating through a number of techniques to improve their performance. For users, the MapReduce job in a

  • Reconstruction of the value of SEQUENCE 2010-06-30

    1.oracle version CREATE OR REPLACE PROCEDURE modify_SEQ IS /**=============================================================================== Definition of control variables ============================================================================