题解 | 糟糕的打谱员

线段树是对的孩子们，因为普通dp的话只能想出来O(n²)的做法只好用线段树O(nlogn)的方法过去了。

开两个线段树，一个是0下棋的时候，另一个是1下棋的时候，每次都在对方的范围里面查找不是以a_i结尾的最大的合法长度就好了

最后把两边最大的长度比一下就好了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
using i128 = __int128;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;

template<class T>
struct SegmentTree {
    struct Info {
        T val;
        Info(){}
        Info(T num): val(num) {}
        Info operator+(const Info& x) const {
            return max(val, x.val);
        }
        void operator+=(const Info& x) {
            *this = *this + x;
        }
    };

    int min_, max_;
    vector<Info> info;
    SegmentTree(int n): min_(1), max_(n), info(4 * n) {}
    SegmentTree(int l, int r): min_(l), max_(r), info(4 * (r - l + 1)) {}
private:
    void pull(int i) {
        info[i] = info[2 * i] + info[2 * i + 1];
    }
    void set(int pos, Info v, int i, int l, int r) {
        if (l == r) {info[i] = v; return;}
        if (pos <= l + (r - l) / 2) set(pos, v, 2 * i, l, l + (r - l) / 2);
        else set(pos, v, 2 * i + 1, l + (r - l) / 2 + 1, r);
        pull(i);
    }
    void add(int pos, Info v, int i, int l, int r) {
        if (l == r) {info[i] += v; return;}
        if (pos <= l + (r - l) / 2) add(pos, v, 2 * i, l, l + (r - l) / 2);
        else add(pos, v, 2 * i + 1, l + (r - l) / 2 + 1, r);
        pull(i);
    }
    Info query(int x, int y, int i, int l, int r) {
        if (l >= x && r <= y) return info[i];
        if (y <= l + (r - l) / 2) return query(x, y, 2 * i, l, l + (r - l) / 2);
        if (x > l + (r - l) / 2) return query(x, y, 2 * i + 1, l + (r - l) / 2 + 1, r);
        return query(x, y, 2 * i, l, l + (r - l) / 2) + query(x, y, 2 * i + 1, l + (r - l) / 2 + 1, r);
    }
    int binarySearch(int i, int l, int r) {
        if (l == r) return l;
        if (info[2 * i].v <= 0) return binarySearch(2 * i, l, l + (r - l) / 2);
        return binarySearch(2 * i + 1, l + (r - l) / 2 + 1, r);
    }
public:
    void set(int i, T v) {
        set(i, v, 1, min_, max_);
    }
    void add(int i, Info v) {
        add(i, v, 1, min_, max_);
    }
    Info query(int l, int r) {
        return query(l, r, 1, min_, max_);
    }
    int binarySearch() {
        return binarySearch(1, min_, max_);
    }
    friend ostream& operator<<(ostream& os, SegmentTree& seg) {
        os << "seg[";
        for (int i = seg.min_; i <= seg.max_; i++) {
            os << seg.query(i, i).val << ",";
        }
        os << ']';
        return os;
    }
};

void solve()
{
    int n;
    cin>>n;
    SegmentTree<int> sg1(10);
    SegmentTree<int> sg2(10);
    for (int i = 1 ; i <= 10 ; i++)
    {
        sg1.set(i,0);
        sg2.set(i,0);
    }
    for (int i = 0 ; i < n ; i++)
    {
        int a,b;
        cin>>a>>b;
        if (a == 0)
        {
            if (b <= 9 && b >= 2)
            sg1.set(b,max(sg2.query(1,b-1).val,sg2.query(b+1,10).val) + 1);
            else if (b == 1) sg1.set(b,sg2.query(2,10).val + 1);
            else if (b == 10) sg1.set(b,sg2.query(1,9).val + 1);
        }
        else
        {
            if (b <= 9 && b >= 2)
            sg2.set(b,max(sg1.query(1,b-1).val,sg1.query(b+1,10).val) + 1);
            else if (b == 1) sg2.set(b,sg1.query(2,10).val + 1);
            else if (b == 10) sg2.set(b,sg1.query(1,9).val + 1);
        }
    }
    cout<<max(sg1.query(1,10).val,sg2.query(1,10).val)<<'\n';
    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int _ = 1;
    std::cin>>_;
    while (_--)
    {
        solve();
    }
    return 0;
}