poj 2352 Stars (树状数组||线段树)

poj 2352题目链接

题意:给出n个星星的位置,一个星星的level定义为其左下角(不严格)星星的数量。

要求统计0到n-1 level的星星各有多少个。

下面是一年前写的树状数组的题解:

依然想不通,智商是硬伤,绝望的想哭,真的想哭。

更新于2015年08月04日01:47:18:

好像有点明白了.....详情看注释

树状数组ac代码:

/*************************************************************************
	> File Name: code/poj/2352.cpp
	> Author: 111qqz
	> Email: rkz2013@126.com 
	> Created Time: 2015年08月04日 星期二 00时33分52秒
 ************************************************************************/
 1#include<iostream>
 2#include<iomanip>
 3#include<cstdio>
 4#include<algorithm>
 5#include<cmath>
 6#include<cstring>
 7#include<string>
 8#include<map>
 9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)  
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=4E4+7;
25int a[N];
26int t[N];
27int x,y;
28int n;
29int lowbit (int x)
30{
31    return x&(-x);
32}
33void update(int x,int c)
34{
35    int i;
36    for ( int i = x ; i <= 32001 ; i = i + lowbit(i))
37    {
38	t[i] = t[i] + c;
39    }
40}
41int sum( int x)
42{
43    int i;
44    int res = 0;
45    for ( int i = x ; i >= 1 ; i = i-lowbit(i))
46    {
47	res = res + t[i];
48    }
49  //  cout<<"x:"<<x<<" res:"<<res<<endl;
50    return res;
51}
52int main()
53{
54    scanf("%d",&n);
55    for ( int i = 0 ; i < n ; i ++ )
56    {
57	scanf("%d %d",&x,&y);
58	a[sum(++x)]++;  // ++x是因为坐标是从0 开始,而树状数组的下标一定是从1开始,不然会TLE
59			// sum(++x)是求 ++x 的level
60			//
61			//
62	update(x,1);   //向上更新,对于每一个比x大的位置,由于x的存在,那些位置的点的level都会增加1
63	               //比如对于星3,因为星1的读入,我向上更新了星2,星3,星4,星5,这时候他们的level都是1
64		       //之后读入星2,更新了星3和星5,星3的level是2,星5的level也是2,之后由于星4,星5的level又加1,为5.
65    }
66    for ( int i = 0 ; i < n ; i ++ )
67    {
68	printf("%d\n",a[i]); //数组a存的是level 为i的点有多少个,即为题目所求。
69    }
70	return 0;
71}

当然用线段树也是可以的。 思路同poj 2481 poj 2481 解题报告

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年09月04日 星期日 14时31分12秒
 4File Name :code/poj/r2352.cpp
 5 ************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=32005;
32int tree[N<<2];//tree的N写成了区间个数的15000,wa了一发。
33int ans[N];
34int n;
35pi a[N];
36void PushUp( int rt)
37{
38    tree[rt] = tree[rt<<1] + tree[rt<<1|1];
39}
40void update(int p,int l,int r,int rt)
41{
42    if (l==r)
43    {
44	tree[rt]++;
45	return;
46    }
47    int m = (l+r)>>1;
48    if (p<=m) update(p,lson);
49    else update(p,rson);
50    PushUp(rt);
51}
52int query(int L,int R,int l,int r,int rt)
53{
54    if (L<=l&&r<=R) return tree[rt];
55    int m = (l+r)>>1;
56    int ret = 0 ;
57    if (L<=m)
58    {
59	int res  =query(L,R,lson);
60	ret = ret + res;
61    }
62    if (R>=m+1)
63    {
64	int res  = query(L,R,rson);
65	ret = ret + res;
66    }
67    return ret;
68}
69int main()
70{
71#ifndef  ONLINE_JUDGE 
72    freopen("code/in.txt","r",stdin);
73#endif
74    scanf("%d",&n);
75    ms(ans,0);
76    for ( int i = 1 ;i  <= n ; i++) scanf("%d%d",&a[i].fst,&a[i].sec),a[i].fst++,a[i].sec++;
77    for ( int i = 1 ; i <= n ; i++)
78    {
79	int tmp = query(1,a[i].fst,1,32001,1);
80	ans[tmp]++;
81	update(a[i].fst,1,32001,1);
82    }
83    for ( int i = 0 ; i <= n-1 ; i++)
84	printf("%d\n",ans[i]);
85#ifndef ONLINE_JUDGE  
86    fclose(stdin);
87#endif
88    return 0;
89}