#include<bits/stdc++.h>
using namespace std;
int n, a[3005], q;
deque<int> qu[3005], qu1, qu2;
bool cmp(deque<int> x, deque<int> y) {
return x.size() > y.size();
}
int query() {
sort(qu + 1, qu + n + 1, cmp);
int res = 0;
for (int i = 1; i <= n; i++) {
if (qu[i].size() * 2 + 1 <= res) break;
for (int j = 1; j < i; j++) {
qu1 = qu[i], qu2 = qu[j];
int k, cnt = 0;
if (qu1.empty() || qu2.empty()) continue;
if (qu1.front() < qu2.front()) qu1.pop_front(), k = 1, cnt++;
else qu2.pop_front(), k = 2, cnt++;
while (!qu1.empty() && !qu2.empty()) {
if (qu1.front() < qu2.front()) {
qu1.pop_front();
if (k != 1) cnt++, k = 1;
} else {
qu2.pop_front();
if (k != 2) cnt++, k = 2;
}
}
if (!qu1.empty() && k != 1) cnt++;
if (!qu2.empty() && k != 2) cnt++;
res = max(res, cnt);
}
}
return res;
}
void update(int k, int c) {
int szk = qu[a[k]].size();
for (int i = 0; i < szk; i++) {
if (qu[a[k]][i] == k) {
for (int j = i + 1; j < szk; j++) {
qu[a[k]][j - 1] = qu[a[k]][j];
}
break;
}
}
qu[a[k]].pop_back();
int szc = qu[c].size();
qu[c].push_back(-1);
for (int i = 0; i < szc; i++) {
if (qu[c][i] > k) {
for (int j = szc - 1; j >= i; j--) {
qu[c][j + 1] = qu[c][j];
}
qu[c][i] = k;
break;
}
}
a[k] = c;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], qu[a[i]].push_back(i);
cin >> q;
if (n == 1 && q == 0) {
cout << 1;
return 0;
}
cout << query() << "\n";
while (q--) {
int k, c;
cin >> k >> c;
update(k, c);
cout << query() << "\n";
}
return 0;
}
1 个赞
P12263 求卡常
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5;
int n, q;
int a[N + 5], tree1[(N + 5) * 4], tree2[(N + 5) * 4], lzytag1[(N + 5) * 4], lzytag2[(N + 5) * 4];
int ls(int x) {
return x << 1;
}
int rs(int x) {
return x << 1 | 1;
}
void pushup1(int x) {
tree1[x] = min(tree1[ls(x)], tree1[rs(x)]);
}
void pushup2(int x) {
tree2[x] = min(tree2[ls(x)], tree2[rs(x)]);
}
void build(int x, int xl, int xr) {
if (xl == xr) {
tree1[x] = a[xl], tree2[x] = a[xl] - xl + 1;
return;
}
int mid = (xl + xr) / 2;
build(ls(x), xl, mid);
build(rs(x), mid + 1, xr);
pushup1(x);
pushup2(x);
}
void addtag1(int x, int xl, int xr, int val) {
lzytag1[x] += val;
tree1[x] += val;
}
void addtag2(int x, int xl, int xr, int val) {
lzytag2[x] += val;
tree2[x] += val;
}
void pushdown1(int x, int xl, int xr) {
int mid = (xl + xr) / 2;
addtag1(ls(x), xl, mid, lzytag1[x]);
addtag1(rs(x), mid + 1, xr, lzytag1[x]);
lzytag1[x] = 0;
}
void pushdown2(int x, int xl, int xr) {
int mid = (xl + xr) / 2;
addtag2(ls(x), xl, mid, lzytag2[x]);
addtag2(rs(x), mid + 1, xr, lzytag2[x]);
lzytag2[x] = 0;
}
void update1(int l, int r, int x, int xl, int xr, int val) {
if (l <= xl && xr <= r) {
addtag1(x, xl, xr, val);
return ;
}
pushdown1(x, xl, xr);
int mid = (xl + xr) / 2;
if (l <= mid) update1(l, r, ls(x), xl, mid, val);
if (r > mid) update1(l, r, rs(x), mid + 1, xr, val);
pushup1(x);
}
void update2(int l, int r, int x, int xl, int xr, int val) {
if (l <= xl && xr <= r) {
addtag2(x, xl, xr, val);
return ;
}
pushdown2(x, xl, xr);
int mid = (xl + xr) / 2;
if (l <= mid) update2(l, r, ls(x), xl, mid, val);
if (r > mid) update2(l, r, rs(x), mid + 1, xr, val);
pushup2(x);
}
signed main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while (q--) {
int l, r, v;
cin >> l >> r >> v;
update1(l, r, 1, 1, n, v);
update2(l, r, 1, 1, n, v);
cout << tree1[1] - max(tree2[1], 0) + 1 << "\n";
}
return 0;
}
1 个赞
题面
1 个赞
找别人吧 
1 个赞
是P11262
写错了是 P12262
1 个赞
比赛那题？？
所以为啥有两个代码？？
我怎么觉得你第二份代码的update1和update2是一样的，还有pushdown和addtag
我现在要调 P12263
1 个赞
杂诗一样的？？
卡常先用快读，加register和inline
快读快写加上试试
1 个赞
结论：\max\{a_i\}-\max\{a_i-i+1\}-1
1 个赞
RE就很烦
1 个赞
找到了
1 个赞
额，你N咋卡着开
@stringdp100005 N = 5e5 + 10
1 个赞