来踩爆这个0分蒟蒻(bushi)谁能帮忙看看这个线段树哪里写挂了
查看原帖
来踩爆这个0分蒟蒻(bushi)谁能帮忙看看这个线段树哪里写挂了
895690
gghack_Nythix楼主2023/1/22 11:53

rt rt

#include <bits/stdc++.h>
#define lid id >> 1
#define rid id >> 1 | 1
#define int long long
using namespace std;
struct segtre{
	struct srg{
		int l,r;
		int val;
	}tr[100005 * 4];
	void build_tr(int id,int l,int r){
		tr[id].l = l,tr[id].r = r;
		if(l == r){
			return ;
		}
		int mid = (l + r)>>1;
		build_tr(lid,l,mid);
		build_tr(rid,mid + 1,r);
		tr[id].val = tr[lid].val + tr[rid].val;
	}
	void modfi(int id,int pos){
		if(tr[id].l == tr[id].r){
			tr[id].val ^= 1;
			return ;
		}
		int mid = (tr[id].l + tr[id].r) >>1;
		if(pos <= mid){
			modfi(lid,pos);
		}
		else{
			modfi(rid,pos);
		}
		tr[id].val = tr[lid].val + tr[rid].val;
	}
	int qur(int id,int l,int r){
		if(l == tr[id].l && r == tr[id].r){
			return tr[id].val;
		}
		int mid = (tr[id].l + tr[id].r) >> 1;
		if(r <= mid){
			return qur(lid,l,r);
		}
		else if(l > mid){
			return qur(rid,l,r);
		}
		else return qur(lid,l,mid) + qur(rid,mid + 1,r);
	}
}treef,treef2;
signed main()
{
	int n,m,k;
	cin >> n >> m >> k;
	treef.build_tr(1,1,n);
	treef2.build_tr(1,1,m);
	for(int i = 1;i <= k;++i){
		int oper;
		cin >> oper;
		if(oper == 1){
			int x,y;
			cin >> x >> y;
			treef2.modfi(1,y);
			treef.modfi(1,x);
		}
		if(oper == 2){
			int x,y,z,a;
			cin >> x >> y >> z >> a;
			int q1 = treef.qur(1,x,z);
			int q2 = treef2.qur(1,y,a);
			cout <<q1*(a-y+1-q2)+q2*(z-x+1-q1) << endl;
		}
	}
	return 0;
}
2023/1/22 11:53
加载中...