社区讨论
帮忙看看树状数组 RE 20 大感谢!
P6619[省选联考 2020 A/B 卷] 冰火战士参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lwlwgf7b
- 此快照首次捕获于
- 2024/05/25 17:19 2 年前
- 此快照最后确认于
- 2024/05/25 19:51 2 年前
是树状数组倍增的 写法,参考了 STAR 的题解。
应该不是空间没开够。
CPP#include <bits/stdc++.h>
using namespace std;
const int maxq = 4e6 + 5;
struct info{
bool typ;
int id, tmpr, engy;
}su[maxq], wd[maxq / 2];
int disc[maxq], cntsu = 0, cntwd = 0, cnt;
int tri[maxq], trf[maxq], sumfire = 0;
int q;
void dctz(); //discretization 离散化
int lowbit(int);
void update(int*, int, int);
int search_pos(int); //通过函数值查找自变量
int search_val(int); //通过自变量查找函数值
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
dctz();
for(int i = 1, idsu = 1, idwd = 1; i <= q; i ++){
if(su[idsu].id == i){
if(su[idsu].typ){
sumfire += su[idsu].engy;
update(trf, su[idsu].tmpr + 1, -su[idsu].engy);
}
else{
update(tri, su[idsu].tmpr, su[idsu].engy);
}
idsu ++;
}
else{
if(wd[idwd].typ){
sumfire -= wd[idwd].engy;
update(trf, wd[idwd].tmpr + 1, wd[idwd].engy);
}
else{
update(tri, wd[idwd].tmpr, -wd[idwd].engy);
}
idwd ++;
}
int pos1 = search_pos(0);
int val1 = search_val(pos1);
int pos2 = pos1 + 1;
int val2 = search_val(pos2);
if(val1 <= 0 && val2 <= 0) cout << "Peace\n";
else if(val1 > val2) cout << disc[pos1] << ' ' << 2 * val1 << '\n';
else{
pos2 = search_pos(val2);
cout << disc[pos2] << ' ' << 2 * val2 << '\n';
}
}
return 0;
}
int search_pos(int val){
int pos = 0;
if(val){
int sum = sumfire;
for(int i = 21; ~i; i --){
int a = pos | (1 << i);
int b = sum + trf[a];
if(a <= cnt && b >= val) pos = a, sum = b;
}
}
else{
int sum = -sumfire;
for(int i = 21; ~i; i --){
int a = pos | (1 << i);
int b = sum + tri[a] - trf[a];
if(a <= cnt && b <= 0) pos = a, sum = b;
}
}
return pos;
}
int search_val(int pos){
if(pos <= 0 || pos > cnt) return 0;
int sumi = 0, sumf = sumfire;
for(int i = pos; i; i -= lowbit(i)){
sumi += tri[i], sumf += trf[i];
}
return min(sumi, sumf);
}
void update(int *tr, int pos, int val){
for(int i = pos; i <= cnt; i += lowbit(i))
tr[i] += val;
return ;
}
int lowbit(int x){
return x & -x;
}
void dctz(){
cin >> q;
for(int i = 1; i <= q; i ++){
int op;
cin >> op;
if(op == 1){
su[++ cntsu].id = i;
cin >> su[cntsu].typ >> su[cntsu].tmpr >> su[cntsu].engy;
}
else cin >> wd[++ cntwd].id;
}
sort(su + 1, su + cntsu + 1, [](info x, info y){
return x.tmpr < y.tmpr || x.tmpr == y.tmpr && x.id < y.id;
});
for(int i = 1, lasttmpr = 0; i <= cntsu; i ++){
if(lasttmpr < su[i].tmpr) cnt ++;
disc[cnt] = lasttmpr = su[i].tmpr, su[i].tmpr = cnt;
}
sort(su + 1, su + cntsu + 1, [](info x, info y){
return x.id < y.id;
});
for(int i = 1, idwd = 1; idwd <= cntwd; i ++)
if(su[i].id == wd[idwd].id){
wd[idwd].typ = su[i].typ;
wd[idwd].tmpr = su[i].tmpr;
wd[idwd].engy = su[i].engy;
idwd ++;
}
return ;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...