标签： 乱搞

假设我们能维护出最终序列的长度L和最终序列出现最多的数的个数cnt，假设$cnt\leq\frac L 2$ ，那么答案是L,这时候我们把序列升序和降序对起来就构造出n的结果。

假设$cnt>\frac L 2$,那么答案是$2(L-cnt)$，我们仍然把序列升序和降序对应起来，答案是$L-(cnt-(L-cnt))=2*(L-cnt)$

比如

“`

1 2 3 3 3 3 3

3 3 3 3 3 2 1

“`

中间有3个3是重了的，那么重的部分有cnt-(L-cnt)个，其中L-cnt表示的是`1 2`的长度，所以总答案是L-(cnt-(L-cnt))

现在的问题在于如何维护出这个众数，并且判定$cnt\leq \frac L 2$是否成立。

考虑一种线性时间求求序列众数(出现次数大于一半)的方法：

令f(i)表示我们从头开始扫到第i个元素的时候(用$a_i$表示)，序列中出现次数最多的数与其他的数出现次数之和的差值。同时我们需要维护这个数是多少(用x来表示)。

每次扫到$a_i$的时候:

– 如果$a_i=x$，那么f(i)=f(i-1)+1,x不变

– 如果$a_i\neq x$,那么f(i)=f(i-1)-1，然后如果$f(i)<0$,那么x变为$a_i$，同时$f(i)$取反。

对于这个题，如果我们要使用这种求众数的方法，核心在于如何考虑操作2（合并两个序列时）如何处理。

我们维护每个序列的f和x，合并两个序列的时候：

– 如果他们的f相同，那么新序列的f不变，x相加。

– 如果他们的f不同，那么考虑下两个序列的哪一个的x比较大。如果他们相同，那么新序列的f就写为0(这时候可能存在两个众数)，x从原来的x里随便选一个。如果他们不同，那x选择为f较大的那一个，同时f设置为较大值减掉较小值。

所以对于这个题，我们先用这种求众数的方法算出来最终序列的众数。

但此时求出来的众数，仅仅是在保证`存在一个出现次数超过序列长度一半时候`的众数，如果不存在这样子的众数，也会得出来一个结果，但是并不具有意义。

所以我们再跑一遍递推，求出来我们上一步求的众数的出现次数，然后我们就可以照着前文所述来算答案了。

*此外，这个题卡常*

我跑了半天性能分析后大概知道了几个卡常的点:

1. 输入量非常巨大，请考虑一次性读入输入数据后自行用缓冲区处理输入。

2. `std::vector`的构造函数非常慢(性能分析显示,$10^6$次调用大约花了80ms)，所以不要使用vector来存储变长的序列，考虑自行分配-回收内存。

3. `State`结构体的构造函数占了大概40ms的时间，考虑强制内联。

另外，读入函数千万不要写错了！不要写成`chr>=’9’`！

#pragma GCC optimize("O2")
#include <assert.h>
#include <inttypes.h>
#include <algorithm>
#include <iostream>
#include <vector>


using int_t = int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 1e6;
char inputbuf[(int(2e8) / 1024) * 1024];
char* head = inputbuf;
inline char nextchar() {
    return *(head++);
}
void initinput() {
    fread(inputbuf, 1024, sizeof(inputbuf) / 1024, stdin);
}
struct State {
    int64_t len;
    int_t mostval;
    int64_t mostcount;
    inline State(int64_t len = 0, int_t mostval = 0, int64_t mostcount = 0)
        : len(len), mostval(mostval), mostcount(mostcount) {}
    State operator+(const State& rhs) const {
        State result(len + rhs.len, 0, 0);
        if (mostval == rhs.mostval)
            result.mostval = mostval,
            result.mostcount = mostcount + rhs.mostcount;
        else {
            if (mostcount > rhs.mostcount) {
                result.mostcount = mostcount - rhs.mostcount;
                result.mostval = mostval;
            } else {
                result.mostcount = rhs.mostcount - mostcount;
                result.mostval = rhs.mostval;
            }
        }
        return result;
    }
};
std::ostream& operator<<(std::ostream& os, const State& state) {
    os << "State{len=" << state.len << ",mostval=" << state.mostval
       << ",mostcount=" << state.mostcount << "}";
    return os;
}
struct Opt {
    int_t type;
    int_t* data;
    int_t datalen;
    int_t x1, x2;
    int64_t mostcount = 0;
} opts[LARGE + 1];
State dp[LARGE + 1];
int_t n;
template <class T>
void read(T& x) {
    x = 0;
    char chr = nextchar();
    while (chr < '0' || chr > '9')
        chr = nextchar();
    while (chr >= '0' && chr <= '9') {
        x = x * 10 + chr - '0';
        chr = nextchar();
    }
    assert(x >= 0);
}
template <class T>
void write(T x) {
    assert(x >= 0);
    if (x > 9)
        write(x / 10);
    putchar('0' + x % 10);
}
int main() {
    // freopen("input.txt", "r", stdin);
    initinput();
    int_t T;
    read(T);
    while (T--) {
        read(n);
        for (int_t i = 1; i <= n; i++) {
            auto& ref = opts[i];
            if (ref.data) {
                delete[] ref.data;
                ref.data = nullptr;
            }
            dp[i] = State();
            read(ref.type);
            if (ref.type == 1) {
                int_t k;
                read(k);
                int_t sum = 0, val = 0;
                ref.data = new int_t[k + 1];
                ref.datalen = k;
                for (int_t i = 1; i <= k; i++) {
                    int_t x;
                    read(x);
                    ref.data[i] = x;
                    if (x == val)
                        sum++;
                    else
                        sum--;
                    if (sum < 0) {
                        sum *= -1, val = x;
                    }
                }
                // ref.seq.shrink_to_fit();
                dp[i] = State(k, val, sum);
            } else {
                read(ref.x1);
                read(ref.x2);
            }
        }
        for (int_t i = 1; i <= n; i++) {
            const auto& ref1 = opts[i];
            if (ref1.type == 2) {
                dp[i] = dp[ref1.x1] + dp[ref1.x2];
            }
        }
#ifdef DEBUG
        for (int_t i = 1; i <= n; i++) {
            cout << "dp " << i << " = " << dp[i] << endl;
        }
#endif
        int_t mostval = dp[n].mostval;
        for (int_t i = 1; i <= n; i++) {
            auto& ref = opts[i];
            if (ref.type == 1)
                ref.mostcount = std::count(ref.data + 1,
                                           ref.data + 1 + ref.datalen, mostval);
            else
                ref.mostcount = opts[ref.x1].mostcount + opts[ref.x2].mostcount;
        }
        int64_t mostcount = opts[n].mostcount;
#ifdef DEBUG
        cout << "final len " << dp[n].len << endl;
        cout << "mostcount " << mostcount << endl;
        cout << "mostval " << mostval << endl;
#endif
        if (mostcount * 2 <= dp[n].len) {
            write(dp[n].len);
        } else {
            write(2 * (dp[n].len - mostcount));
        }
        puts("");
    }
    return 0;
}