「团队训练赛」ShanDong Multi-University Training #3

A - Ant colony

题目描述：

给你n个数a[i]，m次询问，每次询问给出一个l, r,问[l, r]中有多少个数a[i]不满足：a[i]可以被该区间所有数整除

思路：

分析一下就可以发现，如果区间内一个数可以被其他所有数整除，那这个数必须等于区间所有数求gcd后的结果

所以我们需要一个数据结构可以维护区间gcd，以及可以维护出区间gcd的数量

这里给出两种方法：

st表 + 二分，用st表维护区间gcd,查询数量的时候，我们可以用一个vector数组来存每个数出现位置，用二分来查就行，但是因为数字是1e9，不能用vector数组，所以可以用map<int, vector>或者是写个离散化再用vector数组存
线段树维护区间gcd的值和区间gcd数量，就是一个简单的不带修改的普通线段树

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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

#define MAX 300000 + 50
int n, m, k, op;
int l, r;
int tr[MAX];
int lg[MAX];
int gg[MAX][30];
map<int, vector<int>>mp;

int gcd(int a, int b){
    if(b) return gcd(b, a % b);
    else return a;
}

void init(){
    for(int i = 1; i <= n; ++i)gg[i][0] = tr[i];
    for(int i = 2; i <= n; ++i){
        lg[i] = lg[i / 2] + 1;
    }
    for(int j = 1; j <= lg[n]; ++j){
        for(int i = 1; i + (1 << j) - 1 <= n; ++i){
            gg[i][j] = gcd(gg[i][j - 1], gg[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int getgcd(int l, int r){
    int len = lg[r - l + 1];
    return gcd(gg[l][len], gg[r - (1 << len) + 1][len]);
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        mp[tr[i]].push_back(i);
    }
    init();
    cin >> m;
    while(m--){
        cin >> l >> r;
        int x = getgcd(l, r);
        cout << r - l + 1 - (upper_bound(mp[x].begin(), mp[x].end(), r) - lower_bound(mp[x].begin(), mp[x].end(), l))<<endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ls (p<<1)
#define rs ((p<<1)|1)
typedef long long ll;
typedef pair <bool,int> pii;

#define MAX 500000 + 50
int n, m, k, op;
int tr[MAX];
int num[MAX];
int gg[MAX];

int gcd(int a, int b){
    if(b) return gcd(b, a % b);
    else return a;
}
struct ran{
    int gg, num;
};
void pushup(int p){
    gg[p] = gcd(gg[ls], gg[rs]);
    num[p] = (gg[ls] == gg[p] ? num[ls] : 0) + (gg[rs] == gg[p] ? num[rs] : 0);
}

void built(int p, int l, int r){
    if(l == r){
        gg[p] = tr[l];
        num[p] = 1;
        return;
    }
    int mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p);
}

ran getans(int p, int l, int r, int s, int t){
    if(s <= l && r <= t){
        return {gg[p], num[p]};
    }
    ran ans = {0, 0};
    int mid = (l + r) / 2;
    if(mid >= s){
        ans = getans(ls, l, mid, s, t);
    }
    if(mid < t){
        ran a = ans;
        ran now = getans(rs, mid + 1, r, s, t);
        ans.gg = gcd(ans.gg, now.gg);
        ans.num = (a.gg == ans.gg ? a.num : 0) + (now.gg == ans.gg ? now.num : 0);
    }
    return ans;
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    built(1, 1, n);
    cin >> m;
    int l, r;
    while(m--){
        cin >> l >> r;
        ran ans = getans(1, 1, n, l, r);
        cout << r - l + 1 - ans.num << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

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

B - New String

题目描述：

重新给你26字母的先后顺序，按照这个顺序重新定义字典序，给你n个字符串，输出第k小的字符串

思路：

根据给出的26个字母用map映射一下，然后写一个字符串的比较函数sort一下再输出就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ls (p<<1)
#define rs ((p<<1)|1)
typedef long long ll;
typedef pair <bool,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
string s;
map<char, int>mp;
struct ran{
    string s;
    bool operator < (const ran &x)const{
        for(int i = 0; i < s.size() && i < x.s.size(); ++i){
            if(mp[s[i]] < mp[x.s[i]])return true;
            else if(mp[s[i]] > mp[x.s[i]])return false;
            else continue;
        }
        return s.size() < x.s.size();
    }
}tr[MAX];

void work(){
    cin >> s;
    for(int i = 0; i < s.size(); ++i){
        mp[s[i]] = i + 1;
    }
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i].s;
    }
    sort(tr + 1, tr + 1 + n);
    cin >> k;
    cout << tr[k].s << endl;
}


int main(){
    io;
    work();
    return 0;
}

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

C - Easy Problem

题目描述：

给你n * m的图,*是障碍物，.是空地

现在有两个人分别在a，b的位置，二人移动的方向是一样的，都会同时向上、下、左、右四个方向移动，如果向某个方向移动的时候，遇到了障碍物或者遇到了边界，则这个人会原地不动，但是另一个人会正常行走，当然如果同一方向都遇到障碍物那就都不能朝那个东西移动，问二者什么时候可以相遇

思路：

观察一下可以发现n才50，满打满算跑满整个地图也才50⁴的情况，很小，直接跑bfs就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define y1 y114514
#define MAX 300000 + 50
int n, m, k, x;

char tr[55][55];
bool vis[55][55][55][55];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int x1, y1, x2, y2;

struct ran{
    int x1, y1, x2, y2, d;
};

bool judge(int x, int y){
    if(x < 1 || x > n || y < 1 || y > n)return false;
    if(tr[x][y] == '*')return false;
    else return true;
}
void bfs(){
    queue<ran>q;
    ran now, nex;
    q.push({x1, y1, x2, y2, 0});
    vis[x1][y1][x2][y2] = 1;
    while(!q.empty()){
        now = q.front();q.pop();
        if(now.x1 == now.x2 && now.y114514 == now.y2){
            cout << now.d << endl;
            return;
        }
        for(int i = 0; i < 4; ++i){
            if(judge(now.x1 + dx[i], now.y114514 + dy[i])){
                nex.x1 = now.x1 + dx[i];
                nex.y114514 = now.y114514 + dy[i];
            }
            else {
                nex.x1 = now.x1;
                nex.y114514 = now.y114514;
            }
            if(judge(now.x2 + dx[i], now.y2 + dy[i])){
                nex.x2 = now.x2 + dx[i];
                nex.y2 = now.y2 + dy[i];
            }
            else{
                nex.x2 = now.x2;
                nex.y2 = now.y2;
            }
            if(vis[nex.x1][nex.y114514][nex.x2][nex.y2])continue;
            nex.d = now.d + 1;
            q.push(nex);

            vis[nex.x1][nex.y114514][nex.x2][nex.y2] = 1;
        }
    }
    cout << "no solution\n";
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> tr[i][j];
            if(tr[i][j] == 'a'){
                tr[i][j] = '.';
                x1 = i;y1 = j;
            }
            else if(tr[i][j] == 'b'){
                tr[i][j] = '.';
                x2 = i;y2 = j;
            }
        }
    }
    bfs();
}


int main(){
    io;
    work();
    return 0;
}
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

D - Maximum Value

题目描述：

给你n个数，选i, j,且满足a[j] >= a[i]，问a[j] % a[i]的最大值

思路：

我们可以先对数组进行排序，排序以后，对于一个数字a[i],我们需要去找一个a[j]，求a[j]%a[i]的最大值，a[j] = k * a[i] + x,x即余数，我们可以通过枚举k，然后二分找到数组中第一个大于等于k*a[i]的位置p，则p-1位置应该是(k-1)*a[i] 到 k * a[i]这a[i]个数中余数最大的那个，对所有的k，我们都计算出余数求一个最大值，这就是对应的a[i]作为除数时能产生的余数，我们对每个i都这样求一遍就可以，复杂度应该是调和级数的，O(nlogn)

注意剪枝，即相同数字找一次就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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

#define MAX 300000 + 50
int n, m, k, op;
int tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
    }
    sort(tr + 1, tr + 1 + n);
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        int x = tr[i];
        if(tr[i] == tr[i - 1])continue;
        if(x == 1)continue;
        while(x - tr[i] <= tr[n]){
            int p = (int)(lower_bound(tr + i + 1, tr + 1 + n, x) - tr);
            ans = max(ans, tr[p - 1] % tr[i]);
            x += tr[i];
        }
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}
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

E - Prefix Equality

题目描述：

给你两个数组ar[i], br[i]，Q次询问，每次询问都给出a, b,问ar[1]到ar[a]的数组成的集合与br[1]到br[b]的数组成的集合是否相同

思路：

哈希一下就行，我搞了三种数组，一个数量数组，一个前缀和的数组，一个前缀积的数组，判断的时候三个都相同就相同

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, y;
ll ar[MAX], br[MAX];
ll sum1[MAX], sum2[MAX];
ll mul1[MAX], mul2[MAX];
ll num1[MAX], num2[MAX];

void work(){
    cin >> n;
    mul1[0] = mul2[0] = 1;
    for(int i = 1; i <= n; ++i)cin >> ar[i];
    for(int i = 1; i <= n; ++i)cin >> br[i];
    set<ll>se;
    for(int i = 1; i <= n; ++i){
        sum1[i] = sum1[i - 1];
        mul1[i] = mul1[i - 1];
        num1[i] = num1[i - 1];
        if(!se.count(ar[i])){
            ++num1[i];
            se.insert(ar[i]);
            sum1[i] += ar[i];
            (mul1[i] *= ar[i]) %= mod7;
        }
    }
    se.clear();
    for(int i = 1; i <= n; ++i){
        sum2[i] = sum2[i - 1];
        mul2[i] = mul2[i - 1];
        num2[i] = num2[i - 1];
        if(!se.count(br[i])){
            ++num2[i];
            se.insert(br[i]);
            sum2[i] += br[i];
            (mul2[i] *= br[i]) %= mod7;
        }
    }
    cin >> m;
    while (m--) {
        cin >> x >> y;
        if(num1[x] == num2[y] && sum1[x] == sum2[y] &&
           mul1[x] == mul2[y])cout << "Yes\n";
        else cout << "No\n";
    }
}


int main(){
    io;
    work();
    return 0;
}
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

G - Optimal Biking Strategy

题目描述：

你现在在0的位置，需要到达p米的位置

有n个自行车站，你只能在自行车的车站站上下车，每花一块钱最多能骑s米，一米都不可以多骑，如果当前的车不能支持从该站点骑到下一个站点，则他不会骑的

问最少需要在地上走多少米

思路：

动态规划

dp[i][j]表示到i米的位置时，花了j元能骑行的最远距离

状态转移也很好想，就是枚举一下最后一次花k元到达的j

我们假设花了k元,则我们需要知道从什么位置花了k元能走尽可能远的距离到达了j，将这个位置记做id，则dp[i][j] = max(dp[i][j - k] + tr[j] - tr[id];

而求id的方法是二分

注意别忘了加上dp[i][j] = min(dp[i][j], dp[i - 1][j])

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, kk;
ll p, s;
ll tr[MAX];
ll id[MAX][7];
ll dp[MAX][7];
void work(){
    scanf("%lld%lld%lld", &n, &p, &s);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &tr[i]);
    }
    scanf("%lld", &kk);
    for(int i = 1; i <= n; ++i){
        id[i][0] = i;
        for(int j = 1; j <= kk; ++j){
            ll pos = tr[i] - j * s;
            id[i][j] = lower_bound(tr + 1, tr + 1 + n, pos) - tr;
        }
    }
    ll ans = 1e18;
    for(int i = 1; i <= n; ++i){
        dp[i][0] = 0;
        for(int j = 1; j <= kk; ++j){
            dp[i][j] = dp[i - 1][j];
            for(int k = 0; k <= j; ++k){
                dp[i][j] = max(dp[i][j], dp[id[i][k]][j - k] + tr[i] - tr[id[i][k]]);
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        ans = min(ans, p - dp[i][kk]);
    }
    cout << ans << endl;
}

int main(){
    io;
    work();
    return 0;
}

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

I - 250-like Number

题目描述：

k = p * q * q * q，p,q都是素数，问小于等于n中有多少个k

思路：

先用欧拉筛筛出1e6内的素数，再枚举每个p，通过二分去计算q的数量

需要注意的是判断p*q*q*q <= n时会爆long long，所以我们可以移项，即判断q*q*q <= n / p

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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

#define MAX 300000 + 50
ll n, m, k, op;

int tot;
ll prim[MAX];
bool vis[1000050];
void init(){
    for(int i = 2; i <= 1000000; ++i){
        if(!vis[i])prim[++tot] = i;
        for(int j = 1; j <= tot && prim[j] * i <= 1000000; ++j){
            vis[prim[j] * i] = 1;
            if(i % prim[j] == 0)break;
        }
    }
}

void work(){
    init();
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= tot && (ll)pow(prim[i], 4) <= n; ++i){
        int l = i + 1, r = tot;
        while(l <= r){
            int mid = (l + r) / 2;
            if(prim[mid] * prim[mid] * prim[mid] > n / prim[i])r = mid - 1;
            else l = mid + 1;
        }
        ans += l - i - 1;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}
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

J - Wrapping Chocolate

题目描述：

n个巧克力，m个盒子，这里的巧克力和盒子都只有长和宽，问能不能把n个巧克力放在不同的盒子里面

思路：

我们将n+m个巧克力和盒子放在一起，按照宽从大到小，长从大到小进行排序，然后用一个multiset来维护盒子中没有被用过的宽大于等于当前巧克力的所有的长，遇到巧克力的时候，就去multiset中二分查找他的长，如果找到了就删掉，找不到就输出No,如果遇到了盒子，则把长赛到multiset中

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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

#define MAX 500000 + 50
int n, m, k, op;
struct ran{
    int x, y;
    bool op;
    bool operator < (const ran &a)const{
        if(x != a.x)return x > a.x;
        else if(y != a.y)return y > a.y;
        else return op > a.op;
    }
}tr[MAX];

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i].x;
    }
    for(int i = 1; i <= n; ++i){
        cin >> tr[i].y;
    }
    for(int i = n + 1; i <= n + m; ++i){
        cin >> tr[i].x;
    }
    for(int i = n + 1; i <= n + m; ++i){
        cin >> tr[i].y;
        tr[i].op = 1;
    }
    sort(tr + 1, tr + 1 + n + m);
    multiset<int>se;
    for(int i = 1; i <= n + m; ++i){
        if(tr[i].op == 0){
            auto x = se.lower_bound(tr[i].y);
            if(x == se.end()){
                cout << "No\n";
                return;
            }
            se.erase(x);
        }
        else{
            se.insert(tr[i].y);
        }
    }
    cout << "Yes\n";
}


int main(){
    io;
    work();
    return 0;
}


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

K - Endless Walk

题目描述：

给你n个点，m条边，问存在多少个点满足以该点为起点可以走到一个环中

思路：

反向建图跑拓扑排序，输出没被塞到队列里面的点的数量即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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

#define MAX 300000 + 50
int n, m, k, op;
int in[MAX];
int x, y;
vector<int>G[MAX];
bool vis[MAX];
void work(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> x >> y;
        G[y].push_back(x);
        ++in[x];
    }
    queue<int>q;
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        if(in[i] == 0){
            q.push(i);
            ++ans;
        }
    }
    while(!q.empty()){
        int u = q.front();q.pop();
        for(auto v : G[u]){
            --in[v];
            if(in[v] == 0){
                q.push(v);
                ++ans;
            }
        }
    }
    cout << n - ans << endl;
}

int main(){
    io;
    work();
    return 0;
}


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

L - Powerful array

题目描述：

给出n个数，m次询问，每次询问都给出l, r，假设区间内有k种数，值为a[k],且每种数出现num[k]次，则区间的价值为 $\sum_{i=1}^{k}{num[k]*num[k] * a[k]}$

求每次查询的区间价值

思路：

莫队板子

简单推一下式子就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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

#define MAX 300000 + 50
int n, m, k, op;
int block;
ll ar[MAX];

int get_block(int x){
    return x / block;
}

struct ran{
    int l, r, id;
    bool operator < (const ran &a)const{
        int x = get_block(l);
        int y = get_block(a.l);
        if(x != y)return x < y;
        else return r < a.r;
    }
}tr[MAX];

ll ans[MAX];
ll num[1000005];
ll cnt;

void add(int id){
    cnt += ar[id] * (2 * num[ar[id]] + 1);
    ++num[ar[id]];
}
void del(int id){
    cnt += ar[id] * (1 - 2 * num[ar[id]]);
    --num[ar[id]];
}

void work(){
    cin >> n >> m;
    block = sqrt(n);
    for(int i = 1; i <= n; ++i)cin >> ar[i];
    for(int i = 1; i <= m; ++i){
        cin >> tr[i].l >> tr[i].r;
        tr[i].id = i;
    }
    sort(tr + 1, tr + 1 + m);
    int l = 1, r = 0;
    for(int i = 1; i <= m; ++i){
        int s = tr[i].l, t = tr[i].r;
        while(r < t)add(++r);
        while(r > t)del(r--);
        while(l < s)del(l++);
        while(l > s)add(--l);
        ans[tr[i].id] = cnt;
    }
    for(int i = 1; i <= m; ++i){
        cout << ans[i] << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}


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

总结

这次比赛有4个abc的题，其中有俩签到题我都做过，就直接写了交了，剩下俩都见过，但是当时没写，正好趁这次比赛补一下

中间写G题的dp的时候写了半天都是wa，换了个姿势就过了，下午对拍研究了一下，发现按照自己的dp的定义来说，应该写一句dp[i][j] = dp[i - 1][j] ，但是比赛的时候没写，所以开始一直wa，后来换个姿势以后就过了

K题确实没想到这么简单，我还在想怎么dfs能少花点时间更新，yj说反向建图跑个拓扑排序就行，一点就通我只能说是

L题赛时看了一眼，知道是个莫队，但是因为我不怎么写数据结构题，没怎么写过莫队，开始就没写，后来9个题的时候就直接下班了，就忘了这个题，刚刚补了一下发现就是sb题

J题巧克力的题确实很妙很妙，虽然我看一眼就知道是排个序然后二分去找找，但是不知道该怎么写，在我和djk写C的时候yj写了一下就过了

C题看的第一眼就想暴力跑bfs，但是刚开始没细想，最后才发现是sb题

A题djk说可以写线段树，但是当时我一看维护区间gcd，直接上st表了，难得遇到一个可以用st表的题，不能浪费了

相关阅读:
我换了一圈儿，又回来了！
JavaScript中的运算符
 GBASE 8C——SQL参考6 sql语法（4）
PHP MYSQLi 过程式准备好语句
 UNIAPP实战项目笔记44 订单页面顶部选项卡有数据页面样式布局和无数据页面样式布局
 HTTP代理反爬虫技术详解
 23种设计模式【创建型模式】详细介绍之【建造者模式】
JavaScript:实现 jugglerSequence杂耍者序列算法（附完整源码）
vue实现响应式改变scss样式
 PyTorch微调权威指南3：使用数据增强
原文地址：https://blog.csdn.net/weixin_51216553/article/details/125473482