E：Three Blocks Palindrome(hard and easy)(樹狀數組 ？ 字首和？)

Three Blocks Palindrome (hard version)

思路

考慮到每個數字的範圍是 1   200 1 ~ 200 1 200，于是我們可以通過枚舉兩側的元素來尋找最優答案。

我們有一個貪心政策，兩側都以我們枚舉的元素作為結尾點，假如我們目前枚舉的數字是1，于是我們将構成 … … 1 ∣ … … … … ∣ 1 … … ……1|…………|1…… ……1∣…………∣1……這種分界線，這樣可以保證兩邊對中間的影響最小，于是我們就可以從 1   n 1 ~ n 1 n來枚舉我們左側的結尾點，然後通過尋找其右側的結尾點來得到中間的最優值。

我們 v e c t o r < i n t > p o s [ i ] vector<int> pos[i] vector<int>pos[i]中記錄的是，值為 i i i的元素從開始到結尾出現的原數組下标， n u m [ i ] num[i] num[i]記錄的是，值位 i i i的元素在原數組中出現的次數，也就是 p o s [ i ] . s i z e ( ) pos[i].size() pos[i].size()是同一個東西。

為了友善查找值，在這裡還記錄用了一個樹狀數組來記錄 t r e e [ i ] [ j ] tree[i][j] tree[i][j]， 表示值為 i i i的元素在原數組中的第 j j j個位置出現過，也就是通過這個來更新我們的樹狀數組。

寫完後發現好像可以不用樹狀數組，直接用一個字首和數組就行，具體的更新過程也是同樹狀數組類似。

詳細的解析看代碼注釋，有些細節不好描述。

樹狀數組版本——代碼

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

const double eps = 1e-7;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    } 
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}

const int N = 2e5 + 10;

int tree[210][N], a[N], num[210], n;

inline int lowbit(int x) {
    return x & (-x);
}

void update(int value, int pos) {
    while(pos <= n) {
        tree[value][pos]++;
        pos += lowbit(pos);
    }
}

int query(int value, int pos) {
    int sum = 0;
    while(pos) {
        sum += tree[value][pos];
        pos -= lowbit(pos);
    }
    return sum;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int _ = read();
    while(_--) {
        n = read();
        vector<int> pos[210];
        for(int i = 1; i <= n; i++) {
            a[i] = read();//普通的輸入更新。
            num[a[i]]++;
            pos[a[i]].pb(i);
            update(a[i], i);
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            int pre = query(a[i], i);//得到包括這個點及其前面有多少個a[i],
            ans = max(ans, pre);//沒這個就會wa，如果想删去這個的話，初始的ans應該設定為max_element(num);
            //如果出現我們在後面找不到分解線的話，就會wa.
            int last = num[a[i]] - pre;//右側分界線的元素在pos[a[i]]數組中的位置
            if(last < pre)  continue;//如果兩側沒法對稱則不用繼續下面步驟了。
            int l = pos[a[i]][pre - 1], r = pos[a[i]][last];
            for(int j = 1; j <= 200; j++)//找到區間(l, r)中的元素的最多出現次數。
                ans = max(ans, pre * 2 + query(j, r - 1) - query(j, l));//簡單的答案更新。
        }
        printf("%d\n", ans);
        for(int i = 1; i <= 200; i++) {
            num[i] = 0;
            for(int j = 1; j <= n; j++)
                tree[i][j] = 0;
        }
    }
    return 0;
}
           

字首和——代碼

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

const double eps = 1e-7;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    } 
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}

const int N = 2e5 + 10;

int tree[210][N], a[N], n;

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int _ = read();
    while(_--) {
        n = read();
        vector<int> pos[210];
        for(int i = 1; i <= n; i++) {
            a[i] = read();
            pos[a[i]].pb(i);
            for(int j = 1; j <= 200; j++)
                tree[j][i] = tree[j][i - 1] + (a[i] == j);
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            int pre = tree[a[i]][i];
            ans = max(ans, pre);
            int last = pos[a[i]].size() - pre;
            if(last < pre)  continue;
            int l = pos[a[i]][pre - 1], r = pos[a[i]][last];
            for(int j = 1; j <= 200; j++)
                ans = max(ans, pre * 2 + tree[j][r - 1] - tree[j][l]);
        }
        printf("%d\n", ans);
    }
    return 0;
}
           

對比