【Codeforces 707E】Garlands

Qizy Fenwick Tree, 数据结构, 解题报告

题目传送门：http://codeforces.com/contest/707/problem/E
中文题面：http://blog.csdn.net/kg20006/article/details/52275809

对于每一个链单独考虑，算对于答案的贡献
时间复杂度：\(O(k \cdot {\log _2}{(n)^2} \cdot (len + q))\)

然后在算贡献那里，可以用二维树状数组
但我的代码跑了1100ms，有一份代码只跑了700ms
于是去看了看，突然想起来，这种不带修改的二维树状数组
可以把询问记下来，按照横坐标排序，然后转化为一维树状数组
好像要稍微快一点，不过我还是写的二维的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;

const int N = 2000+9;
const int M = 4000000+9;
const int INF = 1000000000;

int q,head[N],Y[M],n,m,k,X[M],W[M],nxt[M],tot,x1[N],x2[N],y1[N],y2[N],tme[N];
LL mat[N][N],vout[N];
queue<int> que[N]; 
char pat[N];

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline void Add(int len, int num){
	static int T = 0;
	for (int i=1;i<=len;i++) {
		nxt[++T] = head[num]; X[T] = read(); 
		Y[T] = read(); W[T] = read(); head[num] = T;
	}
}

inline void modify(int x, int y, int w){
	for (int j=y;j<=m;j+=lowbit(j))
		for (int i=x;i<=n;i+=lowbit(i))
			mat[i][j] += w; 
}

inline LL query(int x, int y){
	LL ret = 0;
	for (int j=y;j;j-=lowbit(j)) 
		for (int i=x;i;i-=lowbit(i))
			ret += mat[i][j];
	return ret;
}

int main(){
	n = read(); m = read(); k = read();
	for (int i=1;i<=k;i++) Add(read(),i);
	q = read(); for (int i=1;i<=q;i++) {
		scanf("%s",pat+1);
		if (pat[1] == 'S') que[read()].push(i);	
		else {
			tme[++tot] = i;
			x1[tot] = read(); y1[tot] = read();
			x2[tot] = read(); y2[tot] = read();
		}
	} 
	for (int i=1;i<=k;i++) que[i].push(INF);
	for (int i=1;i<=k;i++) {
		for (int j=head[i];j;j=nxt[j]) modify(X[j],Y[j],W[j]);
		int sta = 1,T=1; while (!que[i].empty()) {
			int w = que[i].front(); que[i].pop(); sta ^= 1;
			while (T <= tot && tme[T] < w) {
				int p = T++; if (sta^1) 		
				vout[p] += query(x1[p]-1,y1[p]-1) + query(x2[p],y2[p]) - query(x1[p]-1,y2[p]) - query(x2[p],y1[p]-1);
			}
		}
		for (int j=head[i];j;j=nxt[j]) modify(X[j],Y[j],-W[j]);
	} 
	for (int i=1;i<=tot;i++) printf("%I64d\n",vout[i]);
	return 0;
}

176 thoughts to “【Codeforces 707E】Garlands”

  70. “4 Songs for the Club” Is a 4 song CD-EP from B-Rock, For Dj’s and Bars and Dance clubs ..”Dance”Features Rockman doing the electronic Vocals on the Chorus. A hand clapping song to get people on tha dance floor ….”Mix It With Tha Water”. Features B-Rocks Team member Pif .. Tha song is an urban street tale with a great Trap Beat….”I Like It Straight” is Bound to be a New Club/ Bar Anthem for the DJ’s to get the crowds up on their feet and to get another drink..LOL…and “Crack Them bottle (Get Fucked Up)” well that’s a story that all party goers live on the weekend! … 4 Dance Hits 4 tha Club.. a great EP for any DJ to have

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *