给定序列
签到题,考虑维护模意义下的前缀和和后缀和,然后如对于 basic_string
然后二分找,但是发现需要删除元素,然后就上了个权值线段树然后在上面乱搞,然而实际上直接用 set
就可以了。
xxxxxxxxxx
1331
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template < typename T = int >
26inline T read(void);
27
28int N, P;
29int w[110000];
30int sum[110000];
31int rsum[110000];
32int ans[110000];
33int mx(-1), rmx(-1);
34basic_string < int > vals;
35
36class SegTree{
37private:
38 int tr[65536 << 2];
39
40
41
42public:
43 void Pushup(int p){
44 tr[p] = tr[LS] + tr[RS];
45 }
46 void Modify(int val, int cnt = 1, int p = 1, int gl = 0, int gr = P - 1){
47 // printf("In mdf val = %d, gl = %d, gr = %d\n", val, gl, gr);
48 // for(int i = 1; i <= 50000000; ++i);
49 if(gl == gr)return tr[p] += cnt, void();
50 if(val <= MID)Modify(val, cnt, LS, gl, MID);
51 else Modify(val, cnt, RS, MID + 1, gr);
52 Pushup(p);
53 }
54 int QueryRight(int p, int gl, int gr){
55 if(gl == gr)return tr[p] ? gl = gr : -1;
56 if(tr[RS])return QueryRight(RS, MID + 1, gr);
57 return QueryRight(LS, gl, MID);
58 }
59 int QueryLeftMost(int val, int p = 1, int gl = 0, int gr = P - 1){
60 if(gl == gr)return gl <= val && tr[p] ? gl : -1;
61 int mx(-1);
62 if(MID <= val)mx = max(mx, QueryRight(LS, gl, MID));
63 else return QueryLeftMost(val, LS, gl, MID);
64 return max(mx, QueryLeftMost(val, RS, MID + 1, gr));
65 }
66 int QueryLastRight(int p = 1, int gl = 0, int gr = P - 1){
67 if(gl == gr)return tr[p] ? gl = gr : -1;
68 if(tr[RS])return QueryLastRight(RS, MID + 1, gr);
69 return QueryLastRight(LS, gl, MID);
70 }
71}st1, st2;
72
73int main(){
74 freopen("clean.in", "r", stdin);
75 freopen("clean.out", "w", stdout);
76 N = read(), P = read();
77 for(int i = 1; i <= N; ++i)
78 w[i] = read(),
79 sum[i] = (sum[i - 1] + w[i]) % P,
80 st1.Modify(sum[i]),
81 mx = max(mx, sum[i]);
82 for(int i = N; i >= 1; --i)
83 rsum[i] = (rsum[i + 1] + w[i]) % P,
84 st2.Modify(rsum[i]),
85 rmx = max(rmx, rsum[i]);
86 // sort(sum + 1, sum + N + 1);
87 // for(int i = 1; i <= N; ++i)vals += sum[i];
88 // sort(vals.begin(), vals.end());
89 for(int i = 1, j = N; i <= N; ++i, --j){
90
91 // auto it = lower_bound(vals.begin(), vals.end(), val);
92 // int ans(-1);
93 // if(it != vals.end())ans = max(ans, (*it - sum[i] + P) % P);
94 // if(it != vals.end() && next(it) != vals.end())ans = max(ans, (*next(it) - sum[i] + P) % P);
95 // if(it != vals.begin())ans = max(ans, (*prev(it) - sum[i] + P) % P);
96 int val = (P - 1 + sum[i - 1]) % P;
97 int ret = st1.QueryLeftMost(val);
98 // printf("QLM1 i = %d, val = %d, ret = %d, sum is %d\n", i, val, ret, sum[i - 1]);
99 if(!~ret)ret = st1.QueryLastRight();
100 ans[i] = max(ans[i], (ret - sum[i - 1] + P) % P);
101 st1.Modify(sum[i], -1);
102 val = (P - 1 + rsum[j + 1]) % P;
103 ret = st2.QueryLeftMost(val);
104 // printf("QLM2 j = %d, val = %d, ret = %d, rsum is %d\n", j, val, ret, rsum[j + 1]);
105 if(!~ret)ret = st2.QueryLastRight();
106 ans[j] = max(ans[j], (ret - rsum[j + 1] + P) % P);
107 st2.Modify(rsum[j], -1);
108 }
109 for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
110 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
111 return 0;
112}
113
114/*
1154 16
1162 7 9 11
117*/
118
119template < typename T >
120inline T read(void){
121 T ret(0);
122 int flag(1);
123 char c = getchar();
124 while(c != '-' && !isdigit(c))c = getchar();
125 if(c == '-')flag = -1, c = getchar();
126 while(isdigit(c)){
127 ret *= 10;
128 ret += int(c - '0');
129 c = getchar();
130 }
131 ret *= flag;
132 return ret;
133}
存在
奇怪题,也没什么阳间部分分,全贪心。。不会。。
题面很长不想简化了。。。。总之题意理解错了暴力寄了。
存在
拼了个
个人认为这道题的关键是需要考虑到之后当前的
看题解才发现 nt 的我忽略了
考虑正解,对于
对于 set
维护即可。
大概就是首先把问题简化一下,发现撤销没有额外代价,于是考虑可以回收的时候回收所有能回收的点的贡献一定是最优的。
于是发现问题转换为仅有两种行进方式,即从
于是问题再次转化,发现从
感觉后几个部分分和离线的部分分还是可想的,在线正解有点智慧了,总之跳了。。
update-2023_02_24 初稿