POJ3468

n个数a[i],m次询问
每次询问：
C l r d 区间每个数+d
Q l r 区间求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// O((N+Q)sqrt(N))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;

ll a[N], sum[N], add[N];    //原数组，区间和，增量标记
int L[N], R[N];     //每段左右端点
int pos[N];     //每个位置属于哪一段
int n, m, t;

void change(int l, int r, ll d)
{
    int p = pos[l], q = pos[r];
    if (p == q)    //同一段,朴素暴力
    {
        for (int i = l;i <= r;i++)   a[i] += d;
        sum[p] += d * (r - l + 1);
    }
    else    //不在同一段
    {
        //大段维护
        for (int i = p + 1;i <= q - 1;i++)   add[i] += d;
        //局部朴素
        for (int i = l;i <= R[p];i++)    a[i] += d;
        sum[p] += d * (R[p] - l + 1);
        for (int i = L[q];i <= r;i++)   a[i] += d;
        sum[q] += d * (r - L[q] + 1);
    }
}

ll ask(int l, int r)
{
    int p = pos[l], q = pos[r];
    ll ans = 0;
    if (p == q)     //同一段
    {
        for (int i = l;i <= r;i++)   ans += a[i];
        ans += add[p] * (r - l + 1);
    }
    else
    {
        for (int i = p + 1;i <= q - 1;i++)
            ans += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = l;i <= R[p];i++)    ans += a[i];
        ans += add[p] * (R[p] - l + 1);
        for (int i = L[q];i <= r;i++)    ans += a[i];
        ans += add[q] * (r - L[q] + 1);
    }
    return ans;
}

void deer()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++)   cin >> a[i];
    //分块
    t = sqrt(n);
    for (int i = 1;i <= t;i++)
    {
        L[i] = (i - 1) * sqrt(n) + 1;
        R[i] = i * sqrt(n);
    }
    if (R[t] < n)
    {
        t++;
        L[t] = R[t - 1] + 1;
        R[t] = n;
    }
    //预处理
    for (int i = 1;i <= t;i++)
    {
        for (int j = L[i];j <= R[i];j++)
        {
            pos[j] = i;
            sum[i] += a[j];
        }
    }
    //指令
    while (m--)
    {
        char op[3];
        int l, r, d;
        cin >> op >> l >> r;
        if (op[0] == 'C')       //加d
        {
            cin >> d;
            change(l, r, d);
        }
        else    cout << ask(l, r) << "\n";  //求和
    }

    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin>>t;
    while (t--)
    {
        deer();
    }

    return 0;
}

蒲公英
求区间众数

solution1:
n个数分为t段
则每段长度l=n/t
以段边界为段点区间，即对于每个数i有：
cnt[i][l][r] (l=kl+1,kl+l)
记录i在l~r的出现次数

询问[l,r]
则对于[l,L)和(R,r]朴素扫描，在cnt[i][L][R]基础上更新答案
回答询问后，再次朴素扫描，复原cnt

O(NT^2+MN/Tlog N)
N和M同一数量级时，令NT^2===M*N/T,得T=N^(3/2)
即O(N^(5/3))

solution2:
n个数分为t段
则每段长度l=n/t
以段边界为段点区间，即对于每个数i有：
cnt[i][l][r] (l=kl+1,kl+l)
记录i在l~r的出现次数

建立vector按顺序存i在a中出现的位置
则对于[l,L)和(R,r]中的每一个元素x，
在vector[x]中二分查找 第一个>=l的数，最后一个<=r的数 ，下标相减得次数

O(NT+MN/Tlog N)
取T=sqrt(Nlog N)
即 O(Nsqrt(Nlog N))

莫队

P1494 [国家集训队] 小 Z 的袜子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 5e4 + 10;
const ll mod = 1e9 + 7;

int n, m, pos[N], c[N];
ll s[N], ans;

struct dat
{
    int l, r, id;
    ll a, b;
}z[N];

bool cmp(dat x, dat y)
{
    if (pos[x.l] == pos[y.l])
        return x.r < y.r;
    return x.l < y.l;
}

bool cmp_id(dat x, dat y)
{
    return x.id < y.id;
}

void update(int p, int add)
{
    ans -= s[c[p]] * s[c[p]];
    s[c[p]] += add;
    ans += s[c[p]] * s[c[p]];
}

void solve()
{
    for (int i = 1, l = 1, r = 0;i <= m;i++)
    {
        for (;r < z[i].r;r++)
            update(r + 1, 1);
        for (;r > z[i].r;r--)
            update(r, -1);
        for (;l < z[i].l;l++)
            update(l, -1);
        for (;l > z[i].l;l--)
            update(l - 1, 1);
        if (z[i].l == z[i].r)
        {
            z[i].a = 0;
            z[i].b = 1;
            continue;
        }
        z[i].a = ans - (z[i].r - z[i].l + 1);
        z[i].b = (z[i].r - z[i].l + 1) * 1ll * (z[i].r - z[i].l);
        ll g = __gcd(z[i].a, z[i].b);
        z[i].a /= g;
        z[i].b /= g;
    }
}

void deer()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
        cin >> c[i];            //原数组
    int block = sqrt(n);    //块数/每块大小
    for (int i = 1;i <= n;i++)
        pos[i] = (i - 1) / block + 1;   //第i个对应的块序号
    for (int i = 1;i <= m;i++)   //询问
    {
        cin >> z[i].l >> z[i].r;
        z[i].id = i;        //询问序号
    }
    sort(z + 1, z + m + 1, cmp);    //排序(先l后r)
    solve();
    sort(z + 1, z + m + 1, cmp_id);
    for (int i = 1;i <= m;i++)
        cout << z[i].a << "/" << z[i].b << "\n";

    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin>>t;
    while (t--)
    {
        deer();
    }

    return 0;
}

P1903 [国家集训队] 数颜色 / 维护队列
在原有的普通莫队上在加一个时间维度