莫队专题

2018-07-03

A. D-query

统计l到r之间有几个数字。莫队裸题

/*
 * Author:  JiangYu
 * Created Time:  2018/6/29 23:07:03
 * File Name: A.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 2e5 + 1024;
struct query{
    int l, r, id; 
}q[N];
int a[N], b[N];
int n, m, P;
bool cmp(const query &o, const query &t) {
    if(o.l / P == t.l / P) return o.r < t.r;
    return o.l / P < t.l / P;
}
int tmp;
int num[N],ans[N];
void add(int x) {
    if(!num[x]) tmp++;
    num[x]++;
}
void del(int x) {
    num[x]--;
    if(!num[x]) tmp--;
}
void solve() {
    P = (int) sqrt(n);
    sort(q+1, q+1+m, cmp);
    int l = 1, r = 0;
    tmp = 0;
    for(int i = 1; i <= m; ++i) {
        while(r < q[i].r) {
            ++r;
            add(a[r]);
        }
        while(r > q[i].r) {
            del(a[r]);
            r--;
        }
        while(l < q[i].l) {
            del(a[l]);
            l++;
        }
        while(l > q[i].l) {
            --l;
            add(a[l]);
        }
        ans[q[i].id] = tmp;
    }
    for(int i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b+1, b+1+n);
    for(int i = 1; i <= n; ++i) {
        a[i] = lower_bound(b+1, b+1+n, a[i]) - b;
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    solve();
    return 0;
}

B. Powerful array

统计l到r的值，值的定义为 $(number_k) ^ 2 * k$ 之和。依旧是莫队裸题

/*
 * Author:  JiangYu
 * Created Time:  2018/6/29 23:07:03
 * File Name: B.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 1e6 + 1024;
struct query{
    int l, r, id; 
}q[N];
int a[N], b[N];
int n, m, P;
bool cmp(const query &o, const query &t) {
    if(o.l / P == t.l / P) return o.r < t.r;
    return o.l / P < t.l / P;
}
ll tmp;
int num[N];
ll ans[N];
void add(int x) {
    //cout << "+" << x;
    tmp -= 1ll*x*num[x]*num[x];
    num[x]++;
    tmp += 1ll*x*num[x]*num[x];
}
void del(int x) {
    //cout << "-"<<x;
    tmp -= 1ll*x*num[x]*num[x];
    num[x]--;
    tmp += 1ll*x*num[x]*num[x];
}
void solve() {
    P = (int) sqrt(n);
    sort(q+1, q+1+m, cmp);
    int l = 1, r = 0;
    tmp = 0;
    for(int i = 1; i <= m; ++i) {
        while(r < q[i].r) {
            ++r;
            add(a[r]);
            //cout << "+" << a[r];
        }
        while(r > q[i].r) {
            //cout << "-" << a[r];
            del(a[r]);
            r--;
        }
        while(l < q[i].l) {
            //cout << "-" << a[l];
            del(a[l]);
            l++;
        }
        while(l > q[i].l) {
            --l;
            add(a[l]);
            //cout << "+"<<a[l];
        }
        ans[q[i].id] = tmp;
    }
    //for(int i = 1; i <= n; ++i) 
    //cout << num[i]<<" ";
    for(int i = 1; i <= m; ++i) {
        printf("%I64d\n", ans[i]);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    solve();
    return 0;
}

C. Chef and Graph Queries

统计l,r两点之间有多少个联通块。不会……

D. Chef and Substrings

统计l到r之间有多少个不同的子串。也是莫队，但是更新好像要用后缀数组搞，暂时不会，先空着（八成永远空着了）。

E. Tree and Queries

一个树，统计l点到r点之间，出现k次以上的颜色的数量。第一步肯定是根据dfs序，将这颗树拆成线段。然后，因为数据量不大，有两种做法。其一是莫队+树状数组，加了一个log，但是很好理解。

/*
 * Author:  JiangYu
 * Created Time:  2018/6/30 15:34:59
 * File Name: E.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N =  1e5 + 1024;
int n, m;
int in[N], out[N], is[N], times;
bool vis[N];
vector<int> g[N];
int P;
struct node{
    int l, r, k, id;
}q[N];
bool cmp(const node & o, const node &t) {
    if(o.l / P == t.l / P) return o.r < t.r;
    return o.l < t.l;
}
int a[N];
int tmp, num[N];
int num_num[N];
int ans[N];
struct BIT {
    int bit[N];
    void init() {
        memset(bit, 0, sizeof bit);
    }
    int lowbit(int k) {
        return k & -k;
    }
    void add(int x, int y) {
        //cout << x<< ":";
        //cout << 0 + lowbit(0);
        if(x <= 0) return;
        while(x < N) {
            bit[x] += y;
            x += lowbit(x);
        }
    }
    int sum(int x) {
        int res = 0;
        if(x <= 0) return 0;
        while(x) {
            res += bit[x];
            x -= lowbit(x);
        }
        return res;
    }
}bit;
void add(int x) {
    num[x]++;
    bit.add(num[x], 1);
    bit.add(num[x] - 1, -1);
}
void del(int x) {
    num[x]--;
    bit.add(num[x] + 1, -1);
    bit.add(num[x], 1);
}
void solve() {
    int l = 1, r = 0;
    for(int i = 1; i <= m; ++i) {
        //cout << "-";
        while(r < q[i].r) {
            r++;
            add(a[is[r]]);
        }
        //cout << "=";
        while(r > q[i].r) {
            del(a[is[r]]);
            r--;
        }
        //cout << "+";
        while(l > q[i].l) {
            --l;
            add(a[is[l]]);
        }
        //cout << ")";
        while(l < q[i].l) {
            del(a[is[l]]);
            ++l;
        }
        //cout << "??";
        ans[q[i].id] = bit.sum(N-1) - bit.sum(q[i].k - 1);
        //cout << endl;
    }
    for(int i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }
}
void dfs(int u) {
    in[u] = ++times;
    is[times] = u;
    vis[u] = 1;
    for(auto v : g[u]) {
        if(vis[v]) continue;
        dfs(v);
    }
    out[u] = times;
}
int main() {
    scanf("%d%d", &n, &m);
    bit.init();
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n-1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].PB(v);
        g[v].PB(u);
    }
    dfs(1);
    P = (int) sqrt(n);
    for(int i = 1; i <= m; ++i) {
        int u, k;
        scanf("%d%d", &u, &k);
        q[i].l = in[u];
        q[i].r = out[u];
        q[i].id = i;
        q[i].k = k;
    }
    sort(q+1, q+1+m, cmp);
    solve();
    return 0;
}

其二是考虑新开一个计数数组，当某一个颜色加1时，就在那个计数数组对应数量的地方加一，再次出现这个颜色也会在新的对应数量的地方加一。一路加上去就好。减少某一个颜色也是这个做法，一路减下去。因为莫队的方式，每次都是在端点更新，所以可以把做法一的树状数组压缩到O(n)。时间只需要原来的1/3

/*
 * Author:  JiangYu
 * Created Time:  2018/6/30 15:34:59
 * File Name: E.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N =  1e5 + 1024;
int n, m;
int in[N], out[N], is[N], times;
bool vis[N];
vector<int> g[N];
int P;
struct node{
    int l, r, k, id;
}q[N];
bool cmp(const node & o, const node &t) {
    if(o.l / P == t.l / P) return o.r < t.r;
    return o.l < t.l;
}
int a[N];
int tmp, num[N];
int num_num[N];
int ans[N];

void add(int x) {
    //cout << " + " << x;
    num[x]++;
    num_num[num[x]]++;
}
void del(int x) {
    //cout << "-" << x;
    num_num[num[x]]--;
    num[x]--;
}
void solve() {
    int l = 1, r = 0;
    for(int i = q[1].l; i <= q[1].r; ++i) {
        num[a[is[i]] ]++;
        num_num[ num[a[is[i]] ] ] ++;
    }
    ans[q[1].id] = num_num[q[1].k];
    l = q[1].l, r = q[1].r;
    //for(int i = 1; i <= n; ++i) {
        //cout << num_num[i] << " ";
    //}
    //cout << endl;
    for(int i = 2; i <= m; ++i) {
        //cout << "-";
        //cout << q[i].l << " " << q[i].k << " " << q[i].id <<endl;
        while(r < q[i].r) {
            r++;
            add(a[is[r]]);
        }
        //cout << "=";
        while(r > q[i].r) {
            del(a[is[r]]);
            r--;
        }
        //cout << "+";
        while(l > q[i].l) {
            --l;
            add(a[is[l]]);
        }
        //cout << ")";
        while(l < q[i].l) {
            del(a[is[l]]);
            ++l;
        }
        //cout << "??";
        ans[q[i].id] = num_num[q[i].k];
        //cout << endl;
    }
    for(int i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }
}
void dfs(int u) {
    in[u] = ++times;
    is[times] = u;
    vis[u] = 1;
    for(auto v : g[u]) {
        if(vis[v]) continue;
        dfs(v);
    }
    out[u] = times;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n-1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].PB(v);
        g[v].PB(u);
    }
    dfs(1);
    P = (int) sqrt(n);
    for(int i = 1; i <= m; ++i) {
        int u, k;
        scanf("%d%d", &u, &k);
        q[i].l = in[u];
        q[i].r = out[u];
        q[i].id = i;
        q[i].k = k;
    }
    sort(q+1, q+1+m, cmp);
    solve();
    return 0;
}

F. Jeff and Removing Periods

在l到r区间内，看是否存在某一个数组，下标全为等差数列。存在答案即为区间内数字的种数，否则为种数加一。我们可以预处理出fl[i], fr[i]. 表示i这个数字往左（往右）数，第一个下标不属于等差数列的位置。然后就是普通莫队了。

/*
 * Author:  JiangYu
 * Created Time:  2018/6/30 17:36:04
 * File Name: F.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)

const int N = 1e5 + 1024;
struct node {
    int l, r, id;
} q[N];
int n, a[N];
int P;
int last[N], pre[N], bac[N];
bool cmp(const node &o, const node &t) {
    if(o.l / P == t.l / P) return o.r < t.r;
    return o.l < t.l;
}
int num[N], cnt, tmp;
int m, fl[N], fr[N];
int ans[N];
void add1(int pos, int l) {
    num[a[pos]]++;
    if(num[a[pos]] == 1) {
        cnt++;
        tmp++;
    }
    else if(fl[pos] >= l && fl[pre[pos]] < l) cnt--;
}
void del1(int pos, int l) {
    num[a[pos]]--;
    if(num[a[pos]] == 0) {
        cnt--;
        tmp--;
    }
    else if(fl[pos] >= l && fl[pre[pos]] < l) cnt++;
}
void add2(int pos, int r) {
    num[a[pos]]++;
    if(num[a[pos]] == 1) {
        cnt++;
        tmp++;
    }
    else if(fr[pos] <= r && fr[bac[pos]] > r) cnt--;
}
void del2(int pos, int r) {
    num[a[pos]]--;
    if(num[a[pos]] == 0) {
        cnt--;
        tmp--;
    }
    else if(fr[pos] <= r && fr[bac[pos]] > r) cnt++;
}
void solve() {
    int l = 1, r = 0;
    for(int i = 1; i <= m; ++i) {
        while( r < q[i].r) {
            r++;
            add1(r, l);
        }
        while( r > q[i].r) {
            del1(r, l);
            r--;
        }
        while( l < q[i].l) {
            del2(l, r);
            l++;
        }
        while( l > q[i].l) {
            l--;
            add2(l, r);
        }
        if(cnt > 0) 
            ans[q[i].id] = tmp;
        else 
            ans[q[i].id] = tmp + 1;
    }
    for(int i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }
}
int main() {
    scanf("%d", &n);
    P = sqrt(n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i) {
        pre[i] = last[a[i]];
        last[a[i]] = i;
        if (pre[ pre[i] ] == 0)
            fl[i] = 0;
        else if (pre[i] - pre[pre[i]] == i - pre[i]) 
            fl[i] = fl[pre[i]];
        else 
            fl[i] = pre[pre[i]];
    }
    CLR(last);
    for(int i = n; i >= 1; --i) {
        bac[i] = last[a[i]];
        last[a[i]] = i;
        if(bac[ bac[i] ] == 0) 
            fr[i] = n+1;
        else if (bac[ bac[i] ] - bac[i] == bac[i] - i) 
            fr[i] = fr[ bac[i] ];
        else 
            fr[i] = bac[ bac[i] ];
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q+1, q+1+m, cmp);
    solve();
    return 0;
}

G. Sherlock and Inversions

统计l到r区间内的逆序对数量，莫队加一个树状数组统计就好了。

/*
 * Author:  JiangYu
 * Created Time:  2018/7/2 11:48:29
 * File Name: G.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 1e5;
struct node{
    int l, r, id;
}q[N];
int n, m, P;
int a[N], b[N];
bool cmp(const node &o, const node &t) {
    if(o.l / P == t.l / P) return o.r < t.r;
    return o.l < t.l;
}
struct BIT {
    int tree[N];
    int n;
    void init(int nn) {
        memset(tree, 0, sizeof tree);
        n = nn + 1;
    }
    int lowbit(int k) {
        return k & -k;
    }
    void add(int x, int y) {
        while(x < n) {
            tree[x] += y;
            x += lowbit(x);
        }
    }
    int sum(int x) {
        int res = 0;
        while(x) {
            res += tree[x];
            x -= lowbit(x);
        }
        return res;
    }
}bit;
int tmp, ans[N];
void add(int pos) {
    tmp += bit.sum(b[pos]-1);
    bit.add(b[pos], 1);
}
void del(int pos) {
    tmp -= bit.sum(b[pos]-1);
    bit.add(b[pos], -1);
}
void add2(int pos, int l) {
    tmp += (pos - l - bit.sum(b[pos]));
    bit.add(b[pos], 1);
}
void del2(int pos, int l) {
    tmp -= (pos - l - bit.sum(b[pos]) + 1);
    bit.add(b[pos], -1);
}
void solve() {
    int l = 1, r = 0;
    for(int i = 1; i <= m; ++i) {
        while(r < q[i].r) {
            r++;
            add2(r, l);
        }
        while(r > q[i].r) {
            del2(r, l);
            r--;
        }
        while(l < q[i].l) {
            del(l);
            l++;
        }
        while(l > q[i].l) {
            l--;
            add(l);
        }
        ans[q[i].id] = tmp;
    }
    for(int i = 1; i <= m; ++i) 
        printf("%d\n", ans[i]);
}
int main() {
    cin >> n;
    bit.init(n);
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(a+1, a+1+n);
    for(int i = 1; i <= n; ++i) {
        b[i] = lower_bound(a+1, a+1+n, b[i]) - a;
    }
    P = sqrt(n);
    cin >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q+1, q+1+m, cmp);
    solve();
    return 0;
}