社区讨论

帮忙看看树状数组 RE 20 大感谢!

P6619[省选联考 2020 A/B 卷] 冰火战士参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lwlwgf7b
此快照首次捕获于
2024/05/25 17:19
2 年前
此快照最后确认于
2024/05/25 19:51
2 年前
查看原帖
是树状数组倍增的 O(nlogn)O(nlogn) 写法,参考了 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 条回复,欢迎继续交流。

正在加载回复...