弱弱的战壕(jdoj1347-vijos1199)
题目大意：给你n个战壕的坐标，每个战壕只能保护其左下方的战壕 ( 明白为什么是弱弱的战壕了吧 ) ，最后输出n行，第 i 行表示保护了i-1个战壕的战壕个数。
注释：n<=15000 每一个战壕的坐标 ( x ,y ) ，x , y<=32000
想法：和清点人数一样，我们也可以通过线段树来维护，对应的，我们选择树状数组 ( 连修改都没有，扯什么扯 ) 。怎么维护呢？我们思考...思考......。其实，我开始的想法是读入，然后统一处理，结果...发现...tmd读不进去啊！！所以，想到了一种别的方式。因为每个战壕之对它的左下角起到作用，所以，我们必须要保证后面处理的点对于前面已经处理过的点没有影响，所以，想到用sort+bool，先按横坐标排序，再按纵坐标排序，这样，就可以干点一维，接下来就是一些基本的东西了，注意细节，即可。
最后，附上丑陋的代码......
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 int tree[32010]; 6 int a[23333]; 7 int n; 8 struct Node 9 { 10 int x,y; 11 }q[15010]; 12 struct Node1 13 { 14 int x,y; 15 int val; 16 }q1[15010]; 17 bool cmp(Node s,Node r) 18 { 19 if(s.x==r.x) return s.y<r.y; 20 return s.x<r.x; 21 } 22 void fix(int t,int r) 23 { 24 for(int i=t;i<=32000;i+=i&-i) 25 { 26 tree[i]+=r; 27 } 28 } 29 int query(int t) 30 { 31 int ans=0; 32 for(int i=t;i;i-=i&-i) 33 { 34 ans+=tree[i]; 35 } 36 return ans; 37 } 38 int main() 39 { 40 scanf("%d",&n); 41 for(int i=1;i<=n;i++) 42 { 43 scanf("%d%d",&q[i].x,&q[i].y); 44 45 } 46 sort(q+1,q+n+1,cmp); 47 int cnt=0; 48 for(int i=1;i<=n;i++) 49 { 50 if(q[i].y!=q1[cnt].y||q[i].x!=q1[cnt].x) 51 { 52 q1[++cnt].x=q[i].x; 53 q1[cnt].y=q[i].y; 54 } 55 else 56 { 57 q1[cnt].val++; 58 } 59 } 60 for(int i=1;i<=cnt;i++) 61 { 62 a[query(q1[i].y)]+=q1[i].val+1; 63 fix(q1[i].y,q1[i].val+1); 64 } 65 for(int i=0;i<=n-1;i++) 66 { 67 printf("%d ",a[i]); 68 } 69 return 0; 70 }
小结：错误
1.没有注意题目的分析——看差题了
2.数组开错，范围开小
转载请注明：http://www.cnblogs.com/ShuraK/p/7857567.html———请经博主允许