U N R A T E D

今回のコンテストは、採点の遅れの影響で、Unratedとさせていただきます。申し訳ありません。 /　Due to the delay in scoring, this contest will be Unrated. We are sorry for the inconvenience.

A. Echo

题意

给定一个字符串。每个字符输出两遍。

代码

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;

int main(){
    int x;cin>>x;
    string s;cin>>s;
    for(auto x:s){
        cout<<x<<x;
    }
    return 0;
}

B. Base 2

题意

给定 A0,A1,…,A63A_0,A_1,\ldots,A_{63} 求 A020,A121,…,A63263A_02^0,A_12^1,\ldots,A_{63}2^{63}。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
ull ans = 0;

int main(){
    for(int i=0;i<=63;i++){
        int x=read();
        if(x==1){
            ans|=(1llu<<i);
        }
    }
    printf("%llu\n",ans);
    return 0;
}

C. Centers

题意

给定一个 1∼n1\sim n 每个数出现三次，长度为 3n3n 的序列。将每个数按照第二次出现的次序排序。

代码

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N = 1e5+5;
bool vis[N];

vector<pii> v;

int main(){
    int n=read();
    for(int i=1;i<=3*n;i++){
        int x=read();
        if(vis[x]){
            v.push_back({i,x});
            vis[x]=0;
        }else{
            vis[x]=1;
        }
    }

    sort(begend(v));
    for(auto p:v){
        printf("%d ",p.second);
    }
    return 0;
}

D. Poisonous Full-Course

题意

有 nn 个物品。物品有好物品和坏物品，以及分数 YY。你的一开始状态为正常。

在正常状态下：

  • 拿好物品，状态还是正常；
  • 拿坏物品，状态变为不正常。

在不正常状态下：

  • 拿好物品，状态变回正常；
  • 不能拿坏物品。

求最大得分。

解法

显然 dp。设 dp[i][0/1]dp[i][0/1] 代表拿到第 ii 个物品，当前状态是正常/不正常的最大得分。

当现在的物品是一个好物品时：

dp[i][0]=max⁡{dp[i−1][0]dp[i−1][0]+Ydp[i−1][1]+Ydp[i][0]=\max\left\{ \begin{aligned} &dp[i-1][0]\\ &dp[i-1][0]+Y\\ &dp[i-1][1]+Y\\ \end{aligned} \right.

dp[i][1]=dp[i−1][1]dp[i][1]=dp[i-1][1]

当现在的物品是一个坏物品时：

dp[i][0]=dp[i−1][0]dp[i][0]=dp[i-1][0]

dp[i][1]=max⁡{dp[i−1][0]+Ydp[i−1][1]dp[i][1]=\max\left\{ \begin{aligned} &dp[i-1][0]+Y\\ &dp[i-1][1]\\ \end{aligned} \right.

代码

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 3e5+5;

ll dp[N][2];

int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        int a=read(), b=read();
        if(a==0){
            dp[i][0]=max({dp[i-1][0]+b,dp[i-1][1]+b,dp[i-1][0]});
            dp[i][1]=dp[i-1][1];
        }else{
            dp[i][1]=max(dp[i-1][0]+b,dp[i-1][1]);
            dp[i][0]=dp[i-1][0];
        }
    }

    printf("%lld\n",max(dp[n][0],dp[n][1]));
    return 0;
}

E. Best Performances

题意

给定一个长度为 nn 的序列。进行 qq 次操作，每次操作修改一个数。在每次操作后，输出序列前 KK 大数的和（KK 为常数）。

解法

维护一个对顶堆。一个用来维护目前是前 KK 大的数 sel，一个用来维护目前不是前 KK 大的数 uns。

  1. 修改的数是前 KK 大
    删除原数*，答案将修改前的数减去。然后将修改后的数插入 uns。从 uns 中取出最大的数插入 sel，更新答案。然后循环当 uns.top() 大于 sel.top() 时，将两个堆顶调换，更新答案。
  2. 修改的数不是前 KK 大
    删除原数*。将修改后的数插入 uns。然后循环当 uns.top() 大于 sel.top() 时，将两个堆顶调换，更新答案。

*注意：每次修改后，应该要删除原来在堆里的对象，但优先队列不支持删除操作。为此，我们为每个堆的对象维护一个 cnt，代表是第几次修改时的对象。在每次调用 .top() 之前，都要确保 .top() 的对象不是过时的。（下面的 while(sel.size() && cnt[sel.top().i]!=sel.top().c)sel.pop();）

代码

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
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N = 5e5+5;

int a[N];
int cnt[N];
bool in[N];

struct Node{
    int v,i,c;
    bool operator<(const Node& rhs)const{
        return v<rhs.v;
    };
    bool operator>(const Node& rhs)const{
        return v>rhs.v;
    }
};

priority_queue<Node,vector<Node>,greater<Node>> sel;
priority_queue<Node> uns;

ll ans;

int main(){
    int n=read(),k=read(),q=read();
    
    for(int i=1;i<=k;i++){
        sel.push({0,i,0});
        in[i]=1;
    }
    for(int i=k+1;i<=n;i++){
        uns.push({0,i,0});
    }

    for(int i=0;i<q;i++){
        int ind=read(),y=read();

        if(in[ind]){
            ans -= a[ind];
            in[ind]=0;
            cnt[ind]++;
            a[ind]=y;

            while(sel.size() && cnt[sel.top().i]!=sel.top().c)sel.pop();
            while(uns.size() && cnt[uns.top().i]!=uns.top().c)uns.pop();


            uns.push({y,ind,cnt[ind]});

            
            while(sel.size() && cnt[sel.top().i]!=sel.top().c)sel.pop();
            while(uns.size() && cnt[uns.top().i]!=uns.top().c)uns.pop();
            
            ans += uns.top().v;
            in[uns.top().i]=1;
            sel.push(uns.top());
            uns.pop();
            

            while(sel.size() && cnt[sel.top().i]!=sel.top().c)sel.pop();
            while(uns.size() && cnt[uns.top().i]!=uns.top().c)uns.pop();
            while(uns.size() && sel.top().v < uns.top().v){
                ans += -sel.top().v+uns.top().v;
                
                auto p1 = sel.top(), p2=uns.top();
                sel.pop();uns.pop();
                sel.push(p2); uns.push(p1);

                in[p1.i]=0;in[p2.i]=1;
                
                while(sel.size() && cnt[sel.top().i]!=sel.top().c)sel.pop();
                while(uns.size() && cnt[uns.top().i]!=uns.top().c)uns.pop();
            }
        }
        else{
            cnt[ind]++;
            a[ind]=y;
            while(uns.size() && cnt[uns.top().i]!=uns.top().c)uns.pop();
            uns.push({a[ind],ind,cnt[ind]});

            
            while(sel.size() && cnt[sel.top().i]!=sel.top().c)sel.pop();
            while(uns.size() && cnt[uns.top().i]!=uns.top().c)uns.pop();

            while(uns.size() && sel.top().v < uns.top().v){

                ans += -sel.top().v+uns.top().v;
                
                auto p1 =sel.top(),p2=uns.top();
                sel.pop();uns.pop();
                sel.push(p2);uns.push(p1);

                in[p1.i]=0;in[p2.i]=1;
                while(sel.size() && cnt[sel.top().i]!=sel.top().c)sel.pop();
                while(uns.size() && cnt[uns.top().i]!=uns.top().c)uns.pop();
            }
        }

        printf("%lld\n",ans);
    }
    return 0;
}

F. Merge Sets

题意

有 NN 个长度为 MM 的序列 S1,S2,…,SNS_1,S_2,\ldots,S_N，所有数两两不同。

对于两个序列 A={a1,a2,…,am}A=\{a_1,a_2,\ldots,a_m\}，B={b1,b2,…,bm}B=\{b_1,b_2,\ldots,b_m\}，定义 f(A,B)f(A,B) 为：

  1. 将两序列放在一起排序；
  2. 序列 AA 的数在排序后的序列里的下标和。

例：A={1,4,6,8}A=\{1,4,6,8\}，B={2,3,7,9}B=\{2,3,7,9\}，排序后为 1,2,3,4,6,7,8,9\textcolor{red}1,2,3,\textcolor{red}4,\textcolor{red}6,7,\textcolor{red}8,9。序列 AA 中，1,4,6,81,4,6,8 的下标分别为 1,4,5,71,4,5,7，故 f(A,B)=1+4+5+7=17f(A,B)=1+4+5+7=17。

现在，请你求出 ∑1≤i<j≤Nf(Si,Sj)\displaystyle \sum_{1\le i < j \le N}f(S_i,S_j)。

解法 1

使用树状数组。首先将一共有 N(N−1)2\dfrac{N(N-1)}{2} 次的 ff 操作中的答案固定一部分处理。所有数的下标都至少是 1∼M1\sim M，每计算一次 ff，答案固定有 M(M+1)2\dfrac{M(M+1)}{2} ，答案先加上 M(M+1)2N(N−1)2\dfrac{M(M+1)}{2}\dfrac{N(N-1)}{2}。

接下来我们考虑对于序列 SiS_i 中的数 aa，它的答案还差哪些没有被统计。事实上，答案的个数就是所有在此之后的序列中小于 aa 的数的个数。因为在之后的每个序列中，每个小于 aa 的数都会恰好把 aa 的下标往后减一位。

因此，不妨我们将序列 SiS_i 中的数 aa 看作一个二元组 (i,a)(i,a)，我们只需要找到所有的 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2) 满足 x1<x2,y1>y2x_1<x_2,y_1>y_2 的数量即可。这是一个二维偏序问题，可以使用树状数组求解。注意我们要将数据先离散化。

具体来说，按照 xx 的顺序处理每个数据，处理到 (x,y)(x,y) 时，只需要加上 y+1∼MAXNy+1\sim \text{MAXN} 范围内的数就可以了。然后再将 yy 的数量加 1。

总复杂度为 O(NMlog⁡(NM))O(NM\log(NM))。

代码 1

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 1e4+5,M=1e2+5;
int t[N*M];
int a[N][M];

int lowbit(int x){return x&(-x);}
void add(int pos,int val){
    for(;pos<N*M;pos+=lowbit(pos)){
        t[pos]+=val;
    }
}
int sum(int pos){
    int res=0;
    for(;pos>0;pos-=lowbit(pos)){
        res += t[pos];
    }
    return res;
}
int sum(int l,int r){
    return sum(r)-sum(l-1);
}

int main(){
    int n=read(),m=read();
    vector<int> v;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
            v.push_back(a[i][j]);
        }
    }
    ll ans = (ll)(n)*(n-1)/2*(m)*(m+1)/2;
    sort(begend(v));    
    int l = v.size();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int p = lower_bound(begend(v),a[i][j])-v.begin()+1;
            ans += sum(p,l);
        }
        for(int j=1;j<=m;j++){
            int p = lower_bound(begend(v),a[i][j])-v.begin()+1;
            add(p,1);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

解法 2 （赛时解法）

好像做复杂了。

使用平衡树。如果你不会平衡树，你只需要知道我们用到了两个操作，① 插入一个数，② 查询一个数在所有数中的排名，且这两个数的复杂度均为 O(log⁡n)O(\log n)。

我们考虑一次性计算 ∑1≤i<xf(Si,Sx)\displaystyle \sum_{1\le i < x}f(S_i,S_x)。
即对于序列 SxS_x，怎么快速计算所有和它配对的 ff 值呢？

首先，不论如何，所有数的下标都至少是 1∼M1\sim M，故答案先加上 M(M+1)2(x−1)\dfrac{M(M+1)}{2}(x-1)。

然后，我们考虑对于 SxS_x 中的数 aa，它对答案的贡献就是前面所有数中比它大的数量。理解一下，aa 会把前面每个序列中比它大的数都往后挤一位，这个就可以用排名操作计算。（也就是和上面一样的二维偏序，只不过用的是平衡树实现的）

总复杂度为 O(NMlog⁡(NM))O(NM\log(NM))。

代码 2

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}


const int N = 1000005;
int rt, tot, fa[N], ch[N][2], val[N], cnt[N], sz[N];

struct Splay {
  void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; }

  bool get(int x) { return x == ch[fa[x]][1]; }

  void clear(int x) {
    ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chk = get(x);
    ch[y][chk] = ch[x][chk ^ 1];
    if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
    ch[x][chk ^ 1] = y;
    fa[y] = x;
    fa[x] = z;
    if (z) ch[z][y == ch[z][1]] = x;
    maintain(y);
    maintain(x);
  }

  void splay(int x) {
    for (int f = fa[x]; f = fa[x], f; rotate(x))
      if (fa[f]) rotate(get(x) == get(f) ? f : x);
    rt = x;
  }

  void ins(int k) {
    if (!rt) {
      val[++tot] = k;
      cnt[tot]++;
      rt = tot;
      maintain(rt);
      return;
    }
    int cur = rt, f = 0;
    while (1) {
      if (val[cur] == k) {
        cnt[cur]++;
        maintain(cur);
        maintain(f);
        splay(cur);
        break;
      }
      f = cur;
      cur = ch[cur][val[cur] < k];
      if (!cur) {
        val[++tot] = k;
        cnt[tot]++;
        fa[tot] = f;
        ch[f][val[f] < k] = tot;
        maintain(tot);
        maintain(f);
        splay(tot);
        break;
      }
    }
  }

  int rk(int k) {
    int res = 0, cur = rt;
    while (1) {
      if (k < val[cur]) {
        cur = ch[cur][0];
      } else {
        res += sz[ch[cur][0]];
        if (k == val[cur]) {
          splay(cur);
          return res + 1;
        }
        res += cnt[cur];
        cur = ch[cur][1];
      }
    }
  }

  int kth(int k) {
    int cur = rt;
    while (1) {
      if (ch[cur][0] && k <= sz[ch[cur][0]]) {
        cur = ch[cur][0];
      } else {
        k -= cnt[cur] + sz[ch[cur][0]];
        if (k <= 0) {
          splay(cur);
          return val[cur];
        }
        cur = ch[cur][1];
      }
    }
  }

  int pre() {
    int cur = ch[rt][0];
    if (!cur) return cur;
    while (ch[cur][1]) cur = ch[cur][1];
    splay(cur);
    return cur;
  }

  int nxt() {
    int cur = ch[rt][1];
    if (!cur) return cur;
    while (ch[cur][0]) cur = ch[cur][0];
    splay(cur);
    return cur;
  }

  void del(int k) {
    rk(k);
    if (cnt[rt] > 1) {
      cnt[rt]--;
      maintain(rt);
      return;
    }
    if (!ch[rt][0] && !ch[rt][1]) {
      clear(rt);
      rt = 0;
      return;
    }
    if (!ch[rt][0]) {
      int cur = rt;
      rt = ch[rt][1];
      fa[rt] = 0;
      clear(cur);
      return;
    }
    if (!ch[rt][1]) {
      int cur = rt;
      rt = ch[rt][0];
      fa[rt] = 0;
      clear(cur);
      return;
    }
    int cur = rt;
    int x = pre();
    fa[ch[cur][1]] = x;
    ch[x][1] = ch[cur][1];
    clear(cur);
    maintain(rt);
  }
} tree;


ll ans = 0;
int maxn = 0;
int main(){
    int n=read(),m=read();
    for(int i=1;i<=n;i++){
        vector<int> v;
        for(int j=1;j<=m;j++)v.push_back(read());
        sort(begend(v));
        if(i!=1){
            ans += (1+m)*m/2 * (i-1);
            for(int x:v){
                tree.ins(x);maxn=max(maxn,x);
                ans += tree.rk(maxn)-tree.rk(x);
            }
        }
        else for(int x:v){
            tree.ins(x);maxn=max(maxn,x);
        }
    }
    printf("%lld\n",ans);
    return 0;
}