CodeCraft-20 (Div. 2)

A. Grade Allocation

time limit per test1 second memory limit per test256 megabytes

n students are taking an exam. The highest possible score at this exam is m. Let \(a_{i}\) be the score of the i-th student. You have access to the school database which stores the results of all students.

You can change each student’s score as long as the following conditions are satisfied:

  • All scores are integers
  • \(0 \leq a_{i} \leq m\)
  • The average score of the class doesn’t change.

You are student 1 and you would like to maximize your own score.

Find the highest possible score you can assign to yourself such that all conditions are satisfied.Input

Each test contains multiple test cases.

The first line contains the number of test cases t\( (1 \le t \le 200)\). The description of the test cases follows.

The first line of each test case contains two integers n and m \((1 \leq n \leq 10^{3}, 1 \leq m \leq 10^{5})\)  — the number of students and the highest possible score respectively.

The second line of each testcase contains n integers \(a_1, a_2, \dots, a_n (0 \leq a_{i} \leq m) \) — scores of the students.Output

For each testcase, output one integer  — the highest possible score you can assign to yourself such that both conditions are satisfied._ExampleinputCopy

2
4 10
1 2 3 4
4 5
1 2 3 4

outputCopy

10
5

Note

In the first case, a = [1,2,3,4], with average of 2.5. You can change array a to [10,0,0,0]. Average remains 2.5, and all conditions are satisfied.

In the second case, \(0 \leq a_{i} \leq 5\). You can change a to [5,1,1,3]. You cannot increase a_{1} further as it will violate condition \(0\le a_i\le m\).

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,m,a[maxn];
void solve(){
	scanf("%d%d",&n,&m);
	ll sum=0;
	rep(i,1,n) scanf("%d",&a[i]),sum+=a[i];
	printf("%lld\n",max(min(sum,1ll*m),1ll*a[1]));
}
int main(){
	int T;cin>>T;
	while(T--) solve();
}


B. String Modification

time limit per test1 second memory limit per test256 megabytes

Vasya has a string s of length n. He decides to make the following modification to the string:

  1. Pick an integer k, \((1 \leq k \leq n)\).
  2. For i from 1 to n-k+1, reverse the substring s[i:i+k-1] of s. For example, if string s is qwer and k = 2, below is the series of transformations the string goes through:
    • qwer (original string)
    • wqer (after reversing the first substring of length 2)
    • weqr (after reversing the second substring of length 2)
    • werq (after reversing the last substring of length 2)Hence, the resulting string after modifying s with k = 2 is werq.

Vasya wants to choose a k such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of k. Among all such k, he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help.

A string a is lexicographically smaller than a string b if and only if one of the following holds:

  • a is a prefix of b, but a \ne b;
  • in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Input

Each test contains multiple test cases.

The first line contains the number of test cases t \((1 \le t \le 5000)\). The description of the test cases follows.

The first line of each test case contains a single integer n \((1 \le n \le 5000)\) — the length of the string s.

The second line of each test case contains the string s of n lowercase latin letters.

It is guaranteed that the sum of n over all test cases does not exceed 5000.Output

For each testcase output two lines:

In the first line output the lexicographically smallest string s’ achievable after the above-mentioned modification.

In the second line output the appropriate value of k (1 \leq k \leq n) that you chose for performing the modification. If there are multiple values of k that give the lexicographically smallest string, output the smallest value of k among them.ExampleinputCopy

6
4
abab
6
qwerty
5
aaaaa
6
alaska
9
lfpbavjsm
1
p

outputCopy

abab
1
ertyqw
3
aaaaa
1
aksala
6
avjsmbpfl
5
p
1

Note

In the first testcase of the first sample, the string modification results for the sample abab are as follows :

  • for k = 1 : abab
  • for k = 2 : baba
  • for k = 3 : abab
  • for k = 4 : babaThe lexicographically smallest string achievable through modification is abab for k = 1 and 3. Smallest value of k needed to achieve is hence 1.

string真香;
枚举k,对于一个k,我们令s1=s[n-k+1,n],s2=s[1,n-k],如果n-k是偶数还需要将s2反转,得到的新串就是s1+s2,比大小即可;

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n;
string s;
void solve(){
	cin>>n>>s;
	string mn=s;
	int ans=1;
	rep(i,1,n){
		string tmp=s.substr(i-1);
		string a=s.substr(0,i-1);
		if((n-i)%2==0) reverse(a.begin(),a.end());
		tmp+=a;
		if(tmp<mn){
			mn=tmp;ans=i;
		}
	}
	cout<<mn<<endl<<ans<<endl;
}
int main(){
	int T;cin>>T;
	while(T--) solve();
}


C. Primitive Primes

time limit per test1.5 seconds memory limit per test256 megabytes

It is Professor R’s last class of his teaching career. Every time Professor R taught a class, he gave a special problem for the students to solve. You being his favourite student, put your heart into solving it one last time.

You are given two polynomials \(f(x) = a_0 + a_1x + \dots + a_{n-1}x^{n-1}\) and \(g(x) = b_0 + b_1x + \dots + b_{m-1}x^{m-1}\), with positive integral coefficients. It is guaranteed that the cumulative GCD of the coefficients is equal to 1 for both the given polynomials. In other words, \(gcd(a_0, a_1, \dots, a_{n-1}) = gcd(b_0, b_1, \dots, b_{m-1}) = 1\). Let \(h(x) = f(x)\cdot g(x)\). Suppose that \(h(x) = c_0 + c_1x + \dots + c_{n+m-2}x^{n+m-2}\).

You are also given a prime number p. Professor R challenges you to find any t such that c_t isn’t divisible by p. He guarantees you that under these conditions such t always exists. If there are several such t, output any of them.

As the input is quite large, please use fast input reading methods.Input

The first line of the input contains three integers, n, m and p\( (1 \leq n, m \leq 10^6, 2 \leq p \leq 10^9)\),  — n and m are the number of terms in f(x) and g(x) respectively (one more than the degrees of the respective polynomials) and p is the given prime number.

It is guaranteed that p is prime.

The second line contains n integers \(a_0, a_1, \dots, a_{n-1} (1 \leq a_{i} \leq 10^{9})\) — a_i is the coefficient of x^{i} in f(x).

The third line contains m integers \(b_0, b_1, \dots, b_{m-1} (1 \leq b_{i} \leq 10^{9})\)  — b_i is the coefficient of \(x^{i} in g(x)\).Output

Print a single integer t \((0\le t \le n+m-2)\)  — the appropriate power of x in h(x) whose coefficient isn’t divisible by the given prime p. If there are multiple powers of x that satisfy the condition, print any.ExamplesinputCopy

3 2 2
1 1 2
2 1

outputCopy

1

inputCopy

2 2 999999937
2 1
3 1

outputCopy

2

Note

In the first test case, f(x) is \(2x^2 + x + 1\) and g(x) is x + 2, their product h(x) being \(2x^3 + 5x^2 + 3x + 2\), so the answer can be 1 or 2 as both 3 and 5 aren’t divisible by 2.

In the second test case, f(x) is x + 2 and g(x) is x + 3, their product h(x) being x^2 + 5x + 6, so the answer can be any of the powers as no coefficient is divisible by the given prime.

随便找f(x)和g(x)中第一个(或最后一个)不是p的倍数的下标,加起来即可;

证明:令\(x_i\)是f(x)中第一个不被p整除的系数,\(x_j\)是g(x)中第一个不被p整除的系数,那么\(x_{0 , (i-1)}\)和\(x_{0 , (j-1)}\)必是p的倍数;
在h(x)中,\(x^{i + j}=(a_0 * b_{i + j} + a_1 * b_{i + j – 1} + …) + a_i * b_j + (a_{i + 1} * b_{j – 1} + a_{i + 2} * b_{j – 2} +…) \),很容易证明,此式中除了\(a_i * b_j \)不是p的倍数外,其他的都能被p整除,因此i+j即为答案

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,m,p,x,y;
int main(){
    scanf("%d%d%d",&n,&m,&p);
    rep(i,0,n-1){
        int a;scanf("%d",&a);
        if(a%p) x=i;
    }
    rep(i,0,m-1){
        int a;scanf("%d",&a);
        if(a%p) y=i;
    } printf("%d\n",x+y);
}


D. Nash Matrix

time limit per test2 seconds memory limit per test256 megabytes

Nash designed an interesting yet simple board game where a player is simply required to follow instructions written on the cell where the player currently stands.

This board game is played on the n\times n board. Rows and columns of this board are numbered from 1 to n. The cell on the intersection of the r-th row and c-th column is denoted by (r, c).

Some cells on the board are called blocked zones. On each cell of the board, there is written one of the following 5 characters  — U, D, L, R or X  — instructions for the player. Suppose that the current cell is (r, c). If the character is R, the player should move to the right cell (r, c+1), for L the player should move to the left cell (r, c-1), for U the player should move to the top cell (r-1, c), for D the player should move to the bottom cell (r+1, c). Finally, if the character in the cell is X, then this cell is the blocked zone. The player should remain in this cell (the game for him isn’t very interesting from now on).

It is guaranteed that the characters are written in a way that the player will never have to step outside of the board, no matter at which cell he starts.

As a player starts from a cell, he moves according to the character in the current cell. The player keeps moving until he lands in a blocked zone. It is also possible that the player will keep moving infinitely long.

For every of the n^2 cells of the board Alice, your friend, wants to know, how will the game go, if the player starts in this cell. For each starting cell of the board, she writes down the cell that the player stops at, or that the player never stops at all. She gives you the information she has written: for each cell (r, c) she wrote:

  • a pair (x,y), meaning if a player had started at (r, c), he would end up at cell (x,y).
  • or a pair (-1,-1), meaning if a player had started at (r, c), he would keep moving infinitely long and would never enter the blocked zone.

It might be possible that Alice is trying to fool you and there’s no possible grid that satisfies all the constraints Alice gave you. For the given information Alice provided you, you are required to decipher a possible board, or to determine that such a board doesn’t exist. If there exist several different boards that satisfy the provided information, you can find any of them.Input

The first line of the input contains a single integer n \((1 \leq n \leq 10^{3}) \) — the side of the board.

The i-th of the next n lines of the input contains 2n integers \(x_1, y_1, x_2, y_2, \dots, x_n, y_n\), where\( (x_j, y_j) (1 \leq x_j \leq n, 1 \leq y_j \leq n, or (x_j,y_j)=(-1,-1))\) is the pair written by Alice for the cell (i, j).Output

If there doesn’t exist a board satisfying the information that Alice gave you, print a single line containing INVALID.

Otherwise, in the first line print VALID. In the i-th of the next n lines, print the string of n characters, corresponding to the characters in the i-th row of the suitable board you found. Each character of a string can either be U, D, L, R or X. If there exist several different boards that satisfy the provided information, you can find any of them.ExamplesinputCopy

2
1 1 1 1
2 2 2 2

outputCopy

VALID
XL
RX

inputCopy

3
-1 -1 -1 -1 -1 -1
-1 -1 2 2 -1 -1
-1 -1 -1 -1 -1 -1

outputCopy

VALID
RRD
UXD
ULL

Note

For the sample test 1 :

The given grid in output is a valid one.

  • If the player starts at (1,1), he doesn’t move any further following X and stops there.
  • If the player starts at (1,2), he moves to left following L and stops at (1,1).
  • If the player starts at (2,1), he moves to right following R and stops at (2,2).
  • If the player starts at (2,2), he doesn’t move any further following X and stops there.

The simulation can be seen below :

For the sample test 2 :

The given grid in output is a valid one, as a player starting at any cell other than the one at center (2,2), keeps moving in an infinitely long cycle and never stops. Had he started at (2,2), he wouldn’t have moved further following instruction X .

The simulation can be seen below :

读题读一年系列,很显然从x点出发开始dfs可以找到所有非无限点的答案,对于-1需要找环;

难点就在找环上,其实找环也和普通dfs一样找就好了,每次从一个-1开始,dfs一次搜完之后把所有搜到的点都指向这个点即可;

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e3+100;
const int mod=(int)1e9+7;
int n,mp[maxn][maxn],vis[maxn][maxn],vis1[maxn][maxn];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char ans[maxn][maxn],s[5]="UDLR";
void dfs(int x,int y,int k){
    vis[x][y]=1; rep(i,0,3){
        int tmpx=x+dir[i][0],tmpy=y+dir[i][1];
        if(tmpx<=0||tmpx>n||tmpy<=0||tmpy>n||vis[tmpx][tmpy]||mp[tmpx][tmpy]!=k)continue;
        ans[tmpx][tmpy]=s[i];
        dfs(tmpx,tmpy,k);
    }
}
int main(){
    scanf("%d",&n);
    rep(i,1,n) rep(j,1,n){
        int x,y; scanf("%d%d",&x,&y);
        if(x==-1&&y==-1) mp[i][j]=-1;
        else mp[i][j]=(x-1)*n+y;
    }
    rep(i,1,n) rep(j,1,n) if(mp[i][j]==(i-1)*n+j)
        ans[i][j]='X',dfs(i,j,(i-1)*n+j);
    rep(i,1,n) rep(j,1,n) if(mp[i][j]==-1&&!vis[i][j]){
        dfs(i,j,-1);
        rep(k,0,3){
            int tmpx=i+dir[k][0],tmpy=j+dir[k][1];
            if(mp[tmpx][tmpy]==-1) ans[i][j]=s[k^1];
        } if(ans[i][j]=='\0') return puts("INVALID"),0;
    }
    rep(i,1,n) rep(j,1,n) if(!vis[i][j]) return puts("INVALID"),0;
    puts("VALID");
    rep(i,1,n) rep(j,1,n) printf(j==n?"%c\n":"%c",ans[i][j]);
}


E. Team Building

time limit per test3 seconds memory limit per test256 megabytes

Alice, the president of club FCB, wants to build a team for the new volleyball tournament. The team should consist of p players playing in p different positions. She also recognizes the importance of audience support, so she wants to select k people as part of the audience.

There are n people in Byteland. Alice needs to select exactly p players, one for each position, and exactly k members of the audience from this pool of n people. Her ultimate goal is to maximize the total strength of the club.

The i-th of the n persons has an integer a_{i} associated with him — the strength he adds to the club if he is selected as a member of the audience.

For each person i and for each position j, Alice knows s_{i, j}  — the strength added by the i-th person to the club if he is selected to play in the j-th position.

Each person can be selected at most once as a player or a member of the audience. You have to choose exactly one player for each position.

Since Alice is busy, she needs you to help her find the maximum possible strength of the club that can be achieved by an optimal choice of players and the audience.Input

The first line contains 3 integers n,p,k \((2 \leq n \leq 10^{5}, 1 \leq p \leq 7, 1 \le k, p+k \le n)\).

The second line contains n integers \(a_{1},a_{2},\ldots,a_{n}. (1 \leq a_{i} \leq 10^{9})\).

The i-th of the next n lines contains p integers \(s_{i, 1}, s_{i, 2}, \dots, s_{i, p}. (1 \leq s_{i,j} \leq 10^{9})\)Output

Print a single integer {res}  — the maximum possible strength of the club.ExamplesinputCopy

4 1 2
1 16 10 3
18
19
13
15

outputCopy

44

inputCopy

6 2 3
78 93 9 17 13 78
80 97
30 52
26 17
56 68
60 36
84 55

outputCopy

377

inputCopy

3 2 1
500 498 564
100002 3
422332 2
232323 1

outputCopy

422899

Note

In the first sample, we can select person 1 to play in the 1-st position and persons 2 and 3 as audience members. Then the total strength of the club will be equal to \(a_{2}+a_{3}+s_{1,1}\).

我们先想没有观众,那就是一个裸的状压dp,dp[i][j]表示前i个人,已经选的球员位置情况为j的最大收益;现在多了一个观众的限制条件;

对于a我们贪心地来做,将n个人按照a降序排,再从头到尾枚举,如果枚举到这个i和j的时候观众人数还不够,那么这个i就必定是观众(因为越往后收益越小),然后正常跑状压就好了;

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
struct node{
    int id,x;
    bool operator<(node b)const{return x>b.x;}
}a[maxn];
int s[maxn][8],pos[maxn],n,p,k;
ll dp[maxn][1<<8];
int main(){
    scanf("%d%d%d",&n,&p,&k);
    rep(i,1,n) scanf("%d",&a[i].x),a[i].id=i;
    sort(a+1,a+n+1);
    rep(i,1,n) pos[a[i].id]=i;
    rep(i,1,n) rep(j,0,p-1) scanf("%d",&s[pos[i]][j]);
    rep(i,1,n){
        rep(j,0,(1<<p)-1){
            int sum=__builtin_popcountll(j);
            dp[i][j]=dp[i-1][j]+(i>sum&&i-sum<=k)*a[i].x;
        }
        rep(j,0,p-1) rep(k,0,(1<<p)-1) if((k>>j)&1)
            dp[i][k]=max(dp[i][k],dp[i-1][k^(1<<j)]+s[i][j]);
    } printf("%lld\n",dp[n][(1<<p)-1]);
}


F. Battalion Strength

time limit per test5 seconds memory limit per test256 megabytes

There are n officers in the Army of Byteland. Each officer has some power associated with him. The power of the i-th officer is denoted by p_{i}. As the war is fast approaching, the General would like to know the strength of the army.

The strength of an army is calculated in a strange way in Byteland. The General selects a random subset of officers from these n officers and calls this subset a battalion.(All 2^n subsets of the n officers can be chosen equally likely, including empty subset and the subset of all officers).

The strength of a battalion is calculated in the following way:

Let the powers of the chosen officers be \(a_{1},a_{2},\ldots,a_{k}, where a_1 \le a_2 \le \dots \le a_k\). The strength of this battalion is equal to \(a_1a_2 + a_2a_3 + \dots + a_{k-1}a_k\). (If the size of Battalion is \leq 1, then the strength of this battalion is 0).

The strength of the army is equal to the expected value of the strength of the battalion.

As the war is really long, the powers of officers may change. Precisely, there will be q changes. Each one of the form i x indicating that \(p_{i}\) is changed to x.

You need to find the strength of the army initially and after each of these q updates.

Note that the changes are permanent.

The strength should be found by modulo \(10^{9}+7\). Formally, let M=\(10^{9}+7\). It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and \(q\not\equiv 0 \bmod M)\). Output the integer equal to \(p\cdot q^{-1} \bmod M\). In other words, output such an integer x that \(0 \leq x < M and x ⋅ q \equiv p \bmod M)\).Input

The first line of the input contains a single integer n\( (1 \leq n \leq 3⋅10^{5})\)  — the number of officers in Byteland’s Army.

The second line contains n integers \(p_{1},p_{2},\ldots,p_{n} (1 \leq p_{i} \leq 10^{9})\).

The third line contains a single integer q \((1 \leq q \leq 3⋅10^{5})\)  — the number of updates.

Each of the next q lines contains two integers i and x \((1 \leq i \leq n, 1 \leq x \leq 10^{9})\), indicating that \(p_{i}\) is updated to x .Output

In the first line output the initial strength of the army.

In i-th of the next q lines, output the strength of the army after i-th update.ExamplesinputCopy

2
1 2
2
1 2
2 1

outputCopy

500000004
1
500000004

inputCopy

4
1 2 3 4
4
1 5
2 5
3 5
4 5

outputCopy

625000011
13
62500020
375000027
62500027

Note

In first testcase, initially, there are four possible battalions

  • {} Strength = 0
  • {1} Strength = 0
  • {2} Strength = 0
  • {1,2} Strength = 2

So strength of army is \(\frac{0+0+0+2}{4} = \frac{1}{2}\)

After changing p_{1} to 2, strength of battallion {1,2} changes to 4, so strength of army becomes 1.

After changing p_{2} to 1, strength of battalion {1,2} again becomes 2, so strength of army becomes \(\frac{1}{2}\).

神仙离散化+经典线段树;

首先考虑无修改的情况,对于一对\(i,j\),满足\(i < j\),他们对答案造成的贡献是\(p_i \cdot p_j\),这个贡献产生的条件是不存在任意一个\(k\)满足\(i < k < j\),那这样的\(i,j\)选到的概率就为\(\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2^{j-i-1}}\),(选到i的概率 * 选到j的概率 * 不选到k的概率),化简之后为\(\frac{1}{2^{i-j+1}}\);
此时这道题的答案就可以表示为\(ans = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \frac {1}{2^{j-i+1}} \cdot p_i \cdot p_j\)
此时我们有了一个\(n^2\)的算法
这个式子其实很好做,它可以化成\(ans = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \frac {p_i}{2^{1-i}} \cdot \frac {p_j}{2^{j}}\)

我们用线段树维护四个值去得到ans,他们分别是:

  • k: \(r-l+1\) (此节点内的点数)
  • val: \(\sum_{i=1}^{k} \sum_{j=i+1}^{k} \frac {1}{2^{j-i+1}} \cdot p_i \cdot p_j\)
  • Lval: \(\sum_{i=1}^{k} \frac {p_i}{2^{1-i}}\)
  • Rval: \(\sum_{j=1}^{k} \frac{p_j}{2^{j}}\)

相信能看到这里的小伙伴一定对这类线段树的模型了如指掌
我们只需要用左右儿子的值去更新父亲节点即可,最后的答案就是t[1].val;

更新方案如下:

对于叶子结点:

  • k:\( 1\)
  • val:\( 0\)
  • Lval: \(p\)
  • Rval: \(\frac{p}{2}\)

非叶子节点:

  • k : \(k_{lson} + k_{rson}\)
  • val : \(val_{lson}+val_{rson}+\frac{Lval_{lson} \cdot Rval_{rson}}{2^{k_{lson}}}\)
  • Lval : \(Lval_{lson} + Lval_{rson} \cdot 2^{k_{lson}}\)
  • Rval : \(Rval_{lson} + \frac {Rval_{rson}}{2^{k_{lson}}}\)

相信这样的更新大家都不陌生(毕竟多校写过6个值的转移),现在的困难其实是离散化;

p高达\(10^{9}\),必要离散化,既然要离散化那肯定要离线掉,我们就把所有的n+q个p值先读进来并且标个号,再去进行离散化,离散化完成之后就可以开一颗n+q的线段树,一开始线段树中那些在询问里面的p值 的离散化坐标 都设为0,每次询问就在线段树上把当前这个修改的index处原本的值 的离散化坐标 的点设为0,再把index这个点 的离散化坐标 设为询问给的值,然后输出答案即可;
妙极!

 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
#define lson rt<<1
#define rson rt<<1|1
#define delf int mid=(l+r)>>1
#define x first
#define id second
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
const ll inv2=500000004;
int n,q,p[maxn],ind[maxn],qu[maxn];
ll p2[maxn],ip2[maxn];//2^i,(1/2)^i
vector<pair<int,int> > v;
map<int,int> pos;
void precal(){
    p2[0]=ip2[0]=1;
    rep(i,1,maxn-10) p2[i]=p2[i-1]*2%mod,ip2[i]=ip2[i-1]*inv2%mod;
}
struct node{ll val,lval,rval,k;}t[maxn<<2];
void pushup(int rt){
    t[rt].val=((t[lson].val+t[rson].val)%mod+t[lson].lval*t[rson].rval%mod*ip2[t[lson].k]%mod)%mod;
    t[rt].lval=(t[lson].lval+t[rson].lval*p2[t[lson].k]%mod)%mod;
    t[rt].rval=(t[lson].rval+t[rson].rval*ip2[t[lson].k]%mod)%mod;
    t[rt].k=t[lson].k+t[rson].k;
}
void build(int l=1,int r=n+q,int rt=1){
    if(l==r){
        if(v[l].id>n) return;//这是询问中新增的点
        t[rt].val=0;t[rt].lval=v[l].x;t[rt].rval=(v[l].x*inv2)%mod;t[rt].k=1;
        return;
    } delf;
    build(l,mid,lson);build(mid+1,r,rson);pushup(rt);
}
void update(int pos,int op,int l=1,int r=n+q,int rt=1){
    if(l==r){
        if(op==0) t[rt].val=t[rt].lval=t[rt].rval=t[rt].k=0;
        else{
            t[rt].val=0;t[rt].lval=v[pos].x;t[rt].rval=(v[pos].x*inv2)%mod;t[rt].k=1;
        } return;
    } delf;
    if(pos<=mid) update(pos,op,l,mid,lson);
    else update(pos,op,mid+1,r,rson);
    pushup(rt);
}
int main(){
    precal();scanf("%d",&n);v.pb({-1,-1});//让vector从1开始
    rep(i,1,n) scanf("%d",&p[i]),v.pb({p[i],i});
    scanf("%d",&q);
    rep(i,1,q) scanf("%d%d",&ind[i],&qu[i]),v.pb({qu[i],n+i});
    sort(v.begin(),v.end());
    rep(i,1,(int)v.size()-1) pos[v[i].id]=i;
    build();printf("%lld\n",t[1].val);
    rep(i,1,q){
        update(pos[ind[i]]=pos[n+i],0);update(pos[ind[i]],1);
        printf("%lld\n",t[1].val);
    }
}

 

CodeCraft-20 (Div. 2)》有1个想法

孤月 发表评论 取消回复