离散化RE
  • 板块P2068 统计和
  • 楼主konyakest
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/7/1 19:35
  • 上次更新2023/10/27 22:08:33
查看原帖
离散化RE
482660
konyakest楼主2022/7/1 19:35

想写个离散化,结果RE了,调不出来,求dalaodalao帮助

// Problem: P2068 统计和
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2068
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
#define int long long
const int maxn=1e5+5;
#define lowbit(x) ((x)&-(x))
int n,w,a[2][maxn];
vector<int>tmp;
char c[maxn];
struct Fentree{
	int a[maxn*2];
	void add(int x,int k){for(;x<=n;x+=lowbit(x)) a[x]+=k;}
	int query(int x){
		int ans=0;
		for(;x;x-=lowbit(x)) ans+=a[x];
		return ans;
	}
}t;
main() { 
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>w;
	F(i,1,w) cin>>c[i]>>a[0][i]>>a[1][i],tmp.push_back(a[0][i]),tmp.push_back(a[1][i]);
	sort(tmp.begin(),tmp.end());
	int _end=unique(tmp.begin(),tmp.end())-tmp.begin();
	cerr<<_end<<endl;
	F(i,1,w){
		if(c[i]=='x') t.add(lower_bound(tmp.begin(),tmp.begin()+_end,a[0][i])-tmp.begin()+1,
					  a[1][i]);
		else{
			int t1=lower_bound(tmp.begin(),tmp.begin()+_end,a[0][i])-tmp.begin()+1,
				t2=lower_bound(tmp.begin(),tmp.begin()+_end,a[1][i])-tmp.begin()+1;
			cout<<t.query(t2)-t.query(t1-1)<<endl;
		}
	}
	return 0; 
}
2022/7/1 19:35
加载中...