Zerojudge d796 區域調查

tags: 競程題解,競程

Timestamp ： 2023/02/28 13:37

這裡我用的是樹套樹，下面就直接放扣了

但我第112~114行那邊的for迴圈好像可以用其他作法替代嗎
網路上也看不到類似的東西
我自己覺得有點白癡 但我想不出來QQ

最後還是AC了 但時間有點緊 1.3s

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pqueue priority_queue
#define pb push_back
#define F first
#define S second
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define cmax(a, b) a = (a > b ? a : b)
#define cmin(a, b) a = (a < b ? a : b)
#define put(x) cout << x << "\n";
#define DB(x) cerr << #x << " " << x << "\n"
#define all(v) v.begin(), v.end()
#define MEM(x, n) memset(x, n, sizeof(x));
#define lowbit(x) x &(-x)
#if !LOCAL
#endif
const int INF = 0x3f3f3f3f3f3f3f3f;
const int P = 1e9+7;
using namespace std;
/******************************************************************************/
int yseg[1200][1200]={};
int ary[300][300]={};
int n,q;
void build2(int l,int r,int pos,int pos2,int x){
	if(l==r){
		yseg[pos][pos2]=ary[x][l];
		return ;
	}
	int m = (l+r)/2;
	build2(l,m,pos,pos2*2,x);
	build2(m+1,r,pos,pos2*2+1,x);
	yseg[pos][pos2]=yseg[pos][pos2*2]+yseg[pos][pos2*2+1];
	return ;
}
void build1(int x1,int y1,int x2,int y2,int pos){
	if(x1==x2){
		build2(y1,y2,pos,1,x1);
		return ;
	}
	int m = (x1+x2)/2;
	build1(x1,y1,m,y2,pos*2);
	build1(m+1,y1,x2,y2,pos*2+1);
	for(int i=1;i<1200;i++){
		yseg[pos][i]=yseg[pos*2][i]+yseg[pos*2+1][i];
	}	
}

int query2(int l,int r,int L,int R,int pos,int pos2){
	if(l==L&&r==R){
		return yseg[pos][pos2];
		cout<<"8787";
	}
	int M = (L+R)/2;
	if(r<=M){
		return query2(l,r,L,M,pos,pos2*2);
	}
	else if(l>M){
		return query2(l,r,M+1,R,pos,pos2*2+1);
	}
	else{
		return query2(M+1,r,M+1,R,pos,pos2*2+1)+query2(l,M,L,M,pos,pos2*2);
	}
}
int query1(int x1,int y1,int x2,int y2,int l,int r,int pos){
	if(l==x1&&r==x2){
		return query2(y1,y2,1,n,pos,1);
	}
	int m=(l+r)/2;
	if(m>=x2){
		return query1(x1,y1,x2,y2,l,m,pos*2);
	}
	else if(x1>m){
		return query1(x1,y1,x2,y2,m+1,r,pos*2+1);
	}
	else{
		return query1(m+1,y1,x2,y2,m+1,r,pos*2+1)+query1(x1,y1,m,y2,l,m,pos*2);
	}
}
void upd2(int l,int r,int cy,int v,int pos,int pos2){
	if(l==r){
		yseg[pos][pos2]+=v;
		return ;
	}
	int M=(l+r)/2;
	if(M>=cy){
		upd2(l,M,cy,v,pos,pos2*2);
	}
	else upd2(M+1,r,cy,v,pos,pos2*2+1);

	yseg[pos][pos2]=yseg[pos][pos2*2]+yseg[pos][pos2*2+1];
	return ;
}
void upd1(int l,int r,int cx,int cy,int v,int pos){
	if(l==r){
		upd2(1,n,cy,v,pos,1);
		return ;
	}
	int m = (l+r)/2;
	if(cx<=m){
		upd1(l,m,cx,cy,v,pos*2);
	}
	else{
		upd1(m+1,r,cx,cy,v,pos*2+1);
	}
	for(int i=1;i<1200;i++){
		yseg[pos][i]=yseg[pos*2][i]+yseg[pos*2+1][i];
	}
}
signed main(){
	AC
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>ary[i][j];
		}
	}
	build1(1,1,n,n,1);
	while(q--){
		int s;
		cin>>s;
		if(s==1){
			int a,b,c,d;
			cin>>a>>b>>c>>d;
			if(a>c)swap(a,c);
			if(b>d)swap(b,d);
			cout<<query1(a,b,c,d,1,n,1)<<"\n";
		}
		else{
			int x,y,v;
			cin>>x>>y>>v;
			int ad = v-ary[x][y];
			ary[x][y]=v;
			upd1(1,n,x,y,ad,1);
		}
	}
}

下面是2維BIT 實作簡單多了 然後實作量也少很多ww
AC(0.7s)

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pqueue priority_queue
#define pb push_back
#define F first
#define S second
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define cmax(a, b) a = (a > b ? a : b)
#define cmin(a, b) a = (a < b ? a : b)
#define put(x) cout << x << "\n";
#define DB(x) cerr << #x << " " << x << "\n"
#define all(v) v.begin(), v.end()
#define MEM(x, n) memset(x, n, sizeof(x));
#define lowbit(x) x &(-x)
#if !LOCAL
#endif
const int INF = 0x3f3f3f3f3f3f3f3f;
const int P = 1e9+7;
using namespace std;
/******************************************************************************/
int bit[300][300]={},n;
void modify(int x,int y,int v){
	for(;x<=n;x+=lowbit(x)){
		for(int cy=y;cy<=n;cy+=lowbit(cy)){
			bit[x][cy]+=v;
		}
	}
}

int query(int x,int y){
	int ret=0;
	for(;x;x-=lowbit(x)){
		for(int cy=y;cy;cy-=lowbit(cy)){
			ret+=bit[x][cy];
		}
	}
	return ret;
}
int ary[300][300]={};
signed main(){
	AC
	int q,k;
	cin>>n>>q;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>k;
			ary[i][j]=k;
			modify(i,j,k);
		}
	}

	while(q--){
		int s;
		cin>>s;
		if(s==2){
			int x,y,v;
			cin>>x>>y>>v;
			int ad = v-ary[x][y];
			ary[x][y]=v;
			modify(x,y,ad);
		}
		else{
			int a,b,c,d;
			cin>>a>>b>>c>>d;
			if(a>c)swap(a,c);
			if(b>d)swap(b,d);
			cout<<query(c,d)-query(c,b-1)-query(a-1,d)+query(a-1,b-1)<<"\n";
		}
	}
}