求子数组 and or gcd lcm等。固定子数组右端点，子数组长度变大，子数组内元素运算值具有单调性，且存在大量相邻项重复，不重复的个数只有log(n)个。设具有这些性质的运算符为$\oplus$

设$S_i$是$a_1\oplus a_2 \oplus \dots \oplus a_i, \ \ a_2 \oplus \dots \oplus a_i,\ \ a_3 \oplus \dots \oplus a_i,\ \ \cdots, \ \ a_{i-1}\oplus a_i,\ \ a_i$的集合, 看似存在$i$种值，但是实际上由于集合去重，最后不重复的值只有不超过$logU$个。所以$S_i$可以由$S_{i-1}$暴力转移 $S_i = S_{i-1}\oplus a_i$，我们可以维护每种值的状态，如：最左端，最右端，出现个数等。

更好实现与理解的map版本

template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

enum MODE { OR, AND, GCD, LCM };
enum BOUND { L, R };

void logtrick(vector<int>& a, MODE mode, BOUND bound) {
    int n = a.size();
    auto opt = [&](int x, int y) {
        if (mode == OR) return x|y;
        if (mode == AND) return x&y;
        if (mode == GCD) return gcd(x, y);
        if (mode == LCM) return lcm(x, y);
        return -1;
    };
    auto extremum = [&](int x, int y) {
        if (bound == L) return min(x, y);
        if (bound == R) return max(x, y);
        return -1;
    };
    map<int,int> mp;
    for (int i=0; i<n; i++) {
        map<int,int> t;
        t[a[i]] = i;
        for (auto [x, y]:mp) {
            int v = opt(a[i], x);
            if (t.count(v)) t[v] = extremum(t[v], y);
            else t[v] = y;
        }
        mp = t;
        cout << i << " " << mp << endl;
    }
}

void logtrick(vector<int>& a, MODE mode) {
    int n = a.size();
    auto opt = [&](int x, int y) {
        if (mode == OR) return x|y;
        if (mode == AND) return x&y;
        if (mode == GCD) return gcd(x, y);
        if (mode == LCM) return lcm(x, y);
        return -1;
    };
    map<int,pair<int,int>> mp;
    for (int i=0; i<n; i++) {
        map<int,pair<int,int>> t;
        t[a[i]] = {i,i};
        for (auto [x, y]:mp) {
            int v = opt(a[i], x);
            if (t.count(v)) {
                t[v].first = min(t[v].first, y.first);
                t[v].second = max(t[v].second, y.second);
            } else {
                t[v] = y;
            }
        }
        mp = t;
        cout << i << " " << mp << endl;
    }
}

一些习题