[TIOJ] 1869. 堆石子遊戲

題目連結:http://tioj.infor.org/problems/1869
本題我一開始以為可以開個N棵線段樹之類的,結果我就TLE了QAQ,後來想想才發現N棵線段樹的話,複雜度是$O(Q N \log N)$難怪會TLE,想了想發現似乎可以樹套樹(二維BIT),畢竟他只有區間和跟單點修改,那就直接做吧XD,複雜度$O(Q \log ^2 N)$
#include <bits/stdc++.h>
using namespace std;

#define N 1024
#define lowbit(x) (x)&(-x)

int BIT[N+10][N+10]={0};
int n;

void edit(int,int,int);
int query(int,int);

int main(){
	scanf("%d",&n);
	int type;
	while(scanf("%d",&type)!=EOF){
		if(type==1){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			x++,y++;
			edit(x,y,z);
		}else{
			int x1,y1,x2,y2;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			x1++,y1++,x2++,y2++;
			int s = query(x2,y2) + query(x1-1,y1-1) - query(x1-1,y2) - query(x2,y1-1);
			printf("%d\n",s);
		}
	}
	return 0;
}

void edit(int x,int y,int v){
	while(x<=n){
		int yy=y;
		while(yy<=n){
			BIT[x][yy]+=v;
			yy+=lowbit(yy);
		}
		x+=lowbit(x);
	}
}

int query(int x,int y){
	int sum=0;
	while(x>0){
		int yy=y;
		while(yy>0){
			sum+=BIT[x][yy];
			yy-=lowbit(yy);
		}
		x-=lowbit(x);
	}
	return sum;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology