posts - 64, comments - 4, trackbacks - 0, articles - 0

2010年11月13日


来源与分析:http://chenjianneng3.blog.163.com/blog/static/128345126201033101044920/

因为是求极值,所以要注意所求的数据范围,特别是最大,最小可能值。

2010 成都赛区的 Error Curves 就是典型的三分:

附上我的程序:

某某程序:


三分法小结:只要解在一点范围内满足凸函数性质就行,通俗点说就是两边夹,从两边不断逼近。

模版化
double Cal(Type a)
{
    /* 根据题目的意思计算 */
}

void Solve(void)
{
    double Left, Right;
    double mid, midmid;
    double mid_value, midmid_value;
    Left = MIN; Right = MAX;
    while (Left + EPS < Right)
    {
        mid = (Left + Right) / 2;
        midmid = (mid + Right) / 2;
        mid_value = Cal(mid);
        midmid_value = Cal(midmid);
        // 假设求解最大极值.
        if (mid_value >= midmid_value) Right = midmid;
        else Left = mid;
    }
}


poj3301cpp代码:
#include <cstdio>
#include 
<cmath>
#include 
<algorithm>
using namespace std;

const double PI = acos(-1.0
);
const double eps = 1e-8
;
const double maxn = 1000
;
int
 n;
double x[35],y[35
];

double cal(double
 a)
{
    
double
  bx ,by ,sx,sy;
    bx 
= by = -maxn ,sx = sy =
 maxn;
    
double
 tx,ty;
    
for (int i = 1; i <= n; i++
)
    {
         //tx,ty为坐标变换后的坐标,具体怎么推得忘了????
        tx 
= x[i] * cos(a) - y[i] *
 sin(a);
        ty 
= y[i] * cos(a) + x[i] *
 sin(a);
        
        bx 
=
 max(tx,bx);
        sx 
=
 min(tx,sx);
        
        by 
=
 max(ty,by);
        sy 
=
 min(ty,sy);
    }
    
return max(bx - sx , by -
 sy);
}

int
 main()
{
    
int
 t,i,j;
    
double
 lf,rt;
    
double
 m1,m2;
    
double
 m1_v,m2_v;
    scanf(
"%d",&
t);
    
while (t--
)
    {
        scanf(
"%d",&
n);
        
for (i = 1; i <= n; i++
)
            scanf(
"%lf %lf",&x[i],&
y[i]);
        lf 
= 0.0; rt = PI/2
;
        
while (lf + eps <
 rt)
        {
            m1 
= (lf + rt) / 2
;
            m2 
= (m1 + rt) / 2
;
            m1_v 
=
 cal(m1);
            m2_v 
=
 cal(m2);
            
if (m1_v <=
 m2_v)
                rt 
=
 m2;
            
else lf =
 m1;
        }
        
double len =
 cal(lf);
        printf(
"%.2lf\n",len*
len);
    }
    
return 0
;
}

posted @ 2010-11-13 21:35 acronix 阅读(601) | 评论 (0)编辑 收藏

     摘要: 题目描述: 给定n 个字符串,求出现在不小于k 个字符串中的最长子串。 解题报告: 将n 个字符串连起来,中间用不相同的且没有出现在字符串中的字符隔开,求后缀数组。然后二分答案,将后缀分成若干组,判断每组的后缀是否出现在不小于k 个的原串中。 注意: 1、题目要求是超过一半有最大的公共子串,即 》 N / 2,并且 N = 1时直接输出;    &n...  阅读全文

posted @ 2010-11-13 00:09 acronix 阅读(1305) | 评论 (0)编辑 收藏

2010年11月5日





//rmq 求得最大最小值的序号。 
// 注意位运算优先级比+低。 
//
被字母(l)和 数字(1)搞了半天,最后终于看出来了 
#include 
<cstdio
>
#include <
algorithm
>
using
 
namespace std;

const int MAX = 
50005;
int rmqMin[MAX][20],rmqMax[MAX][
20];
int n,q;

void make_rmq(int len,
int a[])
{
     
int i,j,k,x1,y1,x2,y2;
     
for (i = 1; i <= len; i
++)
         rmqMin[i][
0= rmqMax[i][0
= i;
     
for (j = 1; (1 << j) <= len; j
++)
         
for (i = 1; i + (1 << j) - 1 <= len; i
++)
         {
             x1 
= rmqMin[i][j-
1];
             y1 
= rmqMin[i + (1<<(j-1))][j-
1];
             x2 
= rmqMax[i][j-
1];
             y2 
= rmqMax[i + (1<<(j-1))][j-
1];
             rmqMin[i][j] 
= a[x1] < a[y1] 
? x1 : y1; 
             rmqMax[i][j] 
= a[x2] > a[y2] 
? x2 : y2;
         }
}

int query_min(int lf,int rt,
int a[])
{
    
int d = rt - lf + 1,k = 
0,x,y;
    
while ((1<<(k+1)) 
< d)
          k 
++;
    x 
= rmqMin[lf][k];
    y 
= rmqMin[rt - (1 << k) + 
1][k];
    
return a[x] < a[y] 
? x : y;
}

int query_max(int lf,int rt,
int a[])
{
    
int d = rt - lf + 1, k = 
0, x, y;
    
while ((1<<(k+1)) 
< d)
          k
++;
    x 
= rmqMax[lf][k];
    y 
= rmqMax[rt - (1<<k) + 
1][k];
    
return a[x] > a[y] 
? x : y;
}

int main()
{
    
int he[MAX],i,lf,rt;
    
while (scanf("%d %d"&n, &q) 
!= EOF)
    {
          
for (i = 1; i <= n ; i
++)
              scanf(
"%d"
&he[i]);
          make_rmq(n,he);
          
for (i = 1; i <= q; i
++)
          {
              scanf(
"%d %d"&lf, 
&rt);
              printf(
"%d\n",he[query_max(lf,rt,he)] 
- he[query_min(lf,rt,he)]);
          }
    } 
    
return 
0;
}

posted @ 2010-11-05 23:41 acronix 阅读(363) | 评论 (0)编辑 收藏

2010年10月29日




题意:自己看吧。

分析:对左边的点从小到大排序,相等则对右边的从小到大排,最后只要求左边的逆序对即可,求逆序对除了树状数组还有归并排序。

注意:边可以达到1000*1000,结果会超int。


cpp代码:

#include <iostream>
#include 
<cstdio>
#include 
<algorithm>
using namespace std;

int
 maxn,n,m,k;
struct
 Point{
    
int
 x,y;
}a[
1000010
];
long long c[1005
];

int Lowbit(int
 i)
{
    
return i&(-
i);
}

long long up(int
 x)
{
    
int i =
 x;
    
long long res = 0
;
    
while (i <=
 maxn)
    {
        res 
+=
 c[i];
        i 
+=
 Lowbit(i);
    }
    
return
 res;
}

void down(int
 x)
{
    
int i =
 x;
    
while (i > 0
)
    {
        c[i]
++
;
        i 
-=
 Lowbit(i);
    }

}


bool cmp(const Point &a,const Point &
b)
{
    
if (a.x ==
 b.x)
        
return a.y <
 b.y;
   
return a.x <
 b.x;
}

int
 main()
{
    
int t,cas = 1
,i;
    
long long
 ans;
    scanf(
"%d "&
t);
    
while (t--
)
    {
        ans 
= 0
;
        scanf(
"%d %d %d",&n,&m,&
k);
        
for (i = 1; i <= m; i++
)
            c[i] 
=  0
;
        maxn 
=
 m;
        
for (i = 1; i <= k; i++
)
        {
            scanf(
"%d %d",&a[i].x, &
a[i].y);
        }
        sort(a
+1, a+1+
k, cmp);
        
for (i = 1; i <= k; i++
)
        {
            ans 
+= up(a[i].y + 1
);
            down(a[i].y);
        }
        printf(
"Test case %d: %I64d\n",cas++
, ans);

    }

    
return 0
;
}


posted @ 2010-10-29 15:23 acronix 阅读(1507) | 评论 (0)编辑 收藏



题意:给每只cow的头尾坐标,求对于每只cow比他壮的cow,壮大的定义就是比他长就是比他壮。

分析:二维变一维,先按左边的坐标按 j 从大到小排列,然后是 i 左边的坐标从小到大,最后处理 i 就行了,跟stars一样。


cpp代码:

#include <cstdio>
#include 
<stdlib.h>
#include 
<algorithm>
#include 
<memory.h>
using namespace std;

int
 maxn;
int c[100010
];
struct
 Cow{
    
int
 s,e;
    
int
 id;
}cow[
100010
];
int cnt[100010
];
int
 n;

bool cmp(const Cow &a,const Cow &
b)
{
    
if (a.e ==
 b.e)
        
return a.s <
 b.s;
    
return a.e >
 b.e;
}

int Lowbit(int
 i)
{
    
return i&(-
i);
}

void up(int
 x)
{
    
int i =
 x;
    
while (i <=
 n)
    {
        c[i] 
+= 1
;
        i 
+=
 Lowbit(i);
    }
}

int down(int
 x)
{
    
int i = x , res = 0
;
    
while (i > 0
)
    {
        res 
+=
 c[i];
        i 
-=
 Lowbit(i);
    }
    
return
 res;
}


int
 main()
{
    
int
 i,x,y;
    
while (scanf("%d",&n) &&
 n)
    {
        maxn 
= 0
;
        memset(c,
0,sizeof
(c));
        
for (i = 1; i <= n ;i++
)
        {
            cnt[i] 
= 0
;
            scanf(
"%d %d",&x,&
y);
            cow[i].s 
= x+1 , cow[i].e = y+1
;
            cow[i].id 
=
 i;
            
if (maxn <
 cow[i].e)
                maxn 
=
 cow[i].e;
        }
        sort(cow
+1,cow+1+
n,cmp);

        
for (i = 1; i <= n;i++
)
        {
            
if (i > 1 && cow[i].s == cow[i-1].s && cow[i].e == cow[i-1
].e)
                cnt[cow[i].id] 
= cnt[cow[i-1
].id];
            
else cnt[cow[i].id] =
 down(cow[i].s);
            up(cow[i].s);
        }

        
for (i = 1; i <= n; i++
)
        {
            
if (i != 1
)
                printf(
" "
);
            printf(
"%d"
,cnt[i]);
        }
        printf(
"\n"
);

    }
    
return 0
;
}
 

posted @ 2010-10-29 15:18 acronix 阅读(116) | 评论 (0)编辑 收藏



题意:给一个二维矩阵,边修改点格的手机的改变数目,边查询区间手机的总数目。

分析:就是Matrix的相反操作。

CPP代码:

#include <iostream>
#include 
<cstdio>
using namespace std;
int
 n;
int c[1030][1030
];

int Lowbit(int
 i)
{
    
return i&(-
i);
}

void up(int x,int y,int
 a)
{
    
int i =
 x,j;
    
while (i <=
 n)
    {
        j 
=
 y;
        
while (j <=
 n)
        {
            c[i][j] 
+=
 a;
            j 
+=
 Lowbit(j);
        }
        i 
+=
 Lowbit(i);
    }
}

int down(int x,int
 y)
{
    
int i = x,j,res = 0
;
    
while (i > 0
)
    {
        j 
=
 y;
        
while (j > 0
)
        {
            res 
+=
 c[i][j];
            j 
-=
 Lowbit(j);
        }
        i 
-=
 Lowbit(i);
    }
    
return
 res;
}

int
 main()
{
    
int
 ins,x,y,x1,y1,a;
    
int
 i,j;
    scanf(
"%d %d",&ins,&
n);
    
for (i = 1; i <= n; i++
)
        
for (j = 1; j <= n; j++
)
          c[i][j] 
= 0
;
    
while (1
)
    {
        scanf(
"%d",&
ins);
        
if (ins == 3
)
            
break
;
        
if (ins == 1
)
        {
            scanf(
"%d %d %d",&x,&y,&
a);
            x
++,y++
;
            up(x,y,a);
        }
        
if (ins == 2
)
        {
            
int ans = 0
;;
            scanf(
"%d %d %d %d",&x,&y,&x1,&
y1);
            x
++,y++,x1++,y1++
;
            ans 
= down(x1,y1) - down(x1,y-1- down(x-1,y1) + down(x-1,y-1
);
            printf(
"%d\n"
,ans);
        }

    }
    
return 0
;
}

posted @ 2010-10-29 15:05 acronix 阅读(105) | 评论 (0)编辑 收藏


题意:自己看吧。

分析:终于通过这道题弄懂了树状数组。

            首先这里我不具体解释 int Lowbit() { i + (- i ) }  来源,我只想强调的是数组C【i】保存的是C[i - 2^k +1] 到C[i] 区间的状态,k 值是 i 二进制表示中末尾0的个数。

           我的理解就是树状数组有两种操作down ,up,都是对区间状态的操作,或者点状态的操作,注意一点的就是只是状态(包括简单的和,个数的

统计,本题翻转次数的统计)的查询与修改。
树状数组的结构就是多叉树形结构,up(即 i + Lowbit(i))是逐级向上处理父区间(注意我说的是父区间),

down (即:i - Lowbit(i))要注意的是 down 不是逐级向下找子区间并进行操作,而是找左边相邻的兄弟区间(我不知道这样描述准不准确,

你可以看那张经典的树状数组的结构图再自己算算就很明了了)。正因为这样,树状数组能方便的查询父区间(UP操作),而不能方便的访问子区间,

只能方便访问左边相邻的兄弟区间(down操作),我觉得这就是它相对于线段树的不足之处,不过还是很强大的了。

           所以,当遇到具体的问题时,只要记住只是区间状态(和,个数,翻转次数。。。。)的访问,具体的操作是用down还是up就很好理解了。

          对于本题,change时是对区间段的翻转次数进行修改所以是down(依次向左对兄弟区间进行修改),当Query时,其实就是统计点覆盖点(x,y)各区间的总翻转次数所以是向上(up)查询父区间的过程,你可以自己模拟一下就很明了。





实现的CPP代码如下:

#include<cstdio>
#include
<cstring>
#include
<algorithm>
using namespace std;

#define N 1005

int mat[N][N];
int
 n;

int lowbit(int
 key){
    
return key&(-
key);
}

int getsum(int x, int
 y){
    
int ans = 0
;
    
for(int i=x; i<=n; i+=
lowbit(i))
        
for(int j=y; j<=n; j+=
lowbit(j))
            ans 
= (ans+mat[i][j])%2
;
    
return
 ans;
}


void change(int x, int
 y){
    
for(int i=x; i>0; i-=
lowbit(i))
        
for(int j=y; j>0; j-=
lowbit(j))
            mat[i][j] 
= (mat[i][j]+1)%2
;
}



int
 main(){
    
int
 t;
    
char si[10
];
    scanf(
"%d",&
t);
    
while(t--
){
        
int
 m;
        scanf(
"%d%d",&n,&
m);
        memset(mat,
0,sizeof
(mat));
        
for(int i=0; i<m; i++
){
            scanf(
"%s"
,si);
            
if(si[0]=='C'
){
                
int
 x1,y1,x2,y2;
                scanf(
"%d%d%d%d",&x1,&y1,&x2,&
y2);
                change(x2,y2);
                change(x1
-1
,y2);
                change(x2,y1
-1
);
                change(x1
-1,y1-1
);
            }
else
{
                
int
 x1,y1;
                scanf(
"%d%d",&x1,&
y1);
                printf(
"%d\n"
,getsum(x1,y1));
            }
        }
        printf(
"\n"
);
    }
    
return 0
;
}

           

posted @ 2010-10-29 14:58 acronix 阅读(276) | 评论 (0)编辑 收藏


具体的就不多解释了,当线段树练练手吧。



#include <cstdio>
#include 
<stdlib.h>
#include 
<cmath>
#include 
<algorithm>
using namespace std;

const int root = 0
;
const double eps = 1e-8
;
struct
 Node{
       
int
 l,r,cover;
       
int
 lnd,rnd;
       
double
 len;
}node[
10000
];
int
 cnt,cnty;
double indx[210
];

struct
 Line{
     
double
  x,y1,y2;
     
bool
 f;
}line[
210
];

void Creat(int p,int l,int
 r)
{
     node[p].l 
= l; node[p].r =
 r;
     node[p].len 
= 0.0; node[p].cover = 0
;
     
if (r - l > 1
)
     {
           
int mid = (l + r) >> 1
;
           node[p].lnd 
= ++
cnt;
           Creat(cnt,l,mid);
           node[p].rnd 
= ++
cnt;
           Creat(cnt,mid,r);
     }
     
else {node[p].lnd = node[p].rnd = -1
;}
}

void upData(int
 p)
{
     
if (node[p].cover > 0
)
     {
         node[p].len 
= indx[node[p].r] -
 indx[node[p].l];
     }
     
else if (node[p].l == node[p].r - 1
)
          {
             node[p].len 
= 0.0
;
             node[p].cover 
= 0
;
          }
          
else
 {
                 
int lf =
 node[p].lnd;
                 
int rf =
 node[p].rnd;
                 node[p].len 
= node[lf].len +
 node[rf].len;
               }
}

void Insert(int p,int l,int
 r)
{
   
//  printf("p = %d,[%d,%d]\n",p,l,r);

     if (l <= node[p].l && node[p].r <= r)
        node[p].cover
++
;
     
else
 {
           
int mid = (node[p].l + node[p].r) >> 1
;
           
if (mid >
 l)
              Insert(node[p].lnd,l,r);
           
if (mid <
 r)
              Insert(node[p].rnd,l,r);
          }
     upData(p);
}

void Delete(int p,int l,int
 r)
{
     
if (l <= node[p].l && node[p].r <=
 r)
        node[p].cover
--
;
     
else
 {
           
int mid = (node[p].l + node[p].r) >> 1
;
           
if (mid >
 l)
              Delete(node[p].lnd,l,r);
           
if (mid <
 r)
              Delete(node[p].rnd,l,r);
          }
     upData(p);
}

int Bi_Search(double
 key)
{
    
int l = 1,r = cnty + 1
,mid;
    
while (l <
 r)
    {
          mid 
= (l + r) >> 1
;
          
if (fabs(indx[mid] - key) <
 eps)
             
return
 mid;
          
else if (indx[mid] + eps <
 key)
                  l 
= mid + 1
;
               
else r =
 mid;
    }
}

void
 Init_Index()
{
     sort(indx
+1,indx+1+
cnty);
     
int m = 1
;
     
for (int i = 2; i <= cnty; i++
)
         
if (fabs(indx[i] - indx[i-1]) >
 eps)
         {
          
//  printf("%lf \n",indx[i]);

            m ++;
            indx[m] 
=
 indx[i];
         }
     cnty 
=
 m;
}

bool cmp(const Line &a,const Line &
b)
{
     
return a.x <
 b.x;
}

int
 main()
{
    
int n,i,j,k,left,right,cas = 1
;
    
double
 x1,x2,y1,y2,prelen,ans,ny1,ny2;
    
while (scanf("%d",&n) &&
 n)
    {
          
for (i = 1; i <= n + n; i+=2
)
          {
              scanf(
"%lf %lf %lf %lf",&x1,&y1,&x2,&
y2);
              ny1 
=
 min(y1,y2);
              ny2 
=
 max(y2,y1);
              line[i].x 
= x1; line[i].y1 = ny1; line[i].y2 =
 ny2;
              line[i].f 
= true
;
              line[i
+1].x = x2; line[i+1].y1 = ny1; line[i+1].y2 =
 ny2;
              line[i
+1].f = false
;
              indx[i] 
= y1; indx[i+1=
 y2;
          }
          sort(line
+1,line+1+n+
n,cmp);
          cnty 
= n +
 n;
          Init_Index();
         
// printf("cnty = %d\n",cnty);

          Creat(root,1,cnty);
          left 
= Bi_Search(line[1
].y1);
          right 
= Bi_Search(line[1
].y2);
          Insert(root,left,right);
          prelen 
=
 node[root].len;
          ans 
= 0
;
          
for (i = 2; i <= n+n ;i++
)
          {
              left 
=
 Bi_Search(line[i].y1);
              right 
=
 Bi_Search(line[i].y2);
              
if
 (line[i].f)
                  Insert(root,left,right);
              
else
 Delete(root,left,right); 
              ans 
+= prelen*(line[i].x - line[i-1
].x);
              prelen 
=
 node[root].len;
          
//    printf("i = %d,len = %lf\n",i,prelen);

          }
          printf(
"Test case #%d\n",cas++
);
          printf(
"Total explored area: %.2lf\n\n"
,ans);
         
    }
    
return 0
;
}

posted @ 2010-10-29 14:17 acronix 阅读(282) | 评论 (0)编辑 收藏


题意:给星星的坐标,定义每个星星左下角(包括正左边和正上方)的星星数是它的level,统计各个level的星星数。

分析:乍看是个二维的统计,因为数据给出的是 y坐标升序,y相等 x坐标升序,所以可以一次读入数据,只要统计 x左边的星星数就行了,

       这道题很好的启示就是二维降一维的方法————按某种规则排序。

下面给出了线段树和树状数组的写法。

点线段树cpp代码如下:


#include <cstdio>
#include 
<algorithm>
using namespace std;

const int root = 0
;
struct
 Node{
       
int
 l,r,cnt;
       
int
 lnd,rnd;
}node[
60005
];
int
 cnt,cntx;
int indx[15010
];
int x[15010],y[15010
];


void Creat(int p,int l,int
 r)
{
     node[p].l 
= l; node[p].r =
 r;
     node[p].cnt 
= 0
;
     
if (l <
 r)
     {
           
int mid = (l + r) >> 1
;
           node[p].lnd 
= ++
cnt;
           Creat(cnt,l,mid);
           node[p].rnd 
= ++
cnt;
           Creat(cnt,mid
+1
,r);
     }
     
else {node[p].lnd = node[p].rnd = -1
;}
}

void upData(int
 p)
{
     
if (node[p].l <
 node[p].r)
        node[p].cnt 
= node[node[p].lnd].cnt +
 node[node[p].rnd].cnt;
}

void Insert(int p,int
 id)
{
     
if (id == node[p].l && id ==
 node[p].r)
         node[p].cnt
++
;
     
else
 {
            
int mid = (node[p].l + node[p].r) >> 1
;
            
if (mid <
 id)
               Insert(node[p].rnd,id);
            
else
 Insert(node[p].lnd,id);
          }
     upData(p);
}

int  query(int p,int l,int
 r)
{
     
int ans = 0
;
     
if (l <= node[p].l && node[p].r <=
 r)
        ans 
=
 node[p].cnt;
     
else
{
          
int mid = (node[p].l + node[p].r) >> 1
;
          
if (mid >=
 l)
             ans 
+=
 query(node[p].lnd,l,r);
          
if (mid <
 r)
             ans 
+=
 query(node[p].rnd,l,r);
         }
     
return
 ans;
}
int Bi_Search(int
 key)
{
    
int l = 1,r = cntx+1
,mid;
    
while (l <
 r)
    {
          mid 
= (l + r) >> 1
;
          
if (indx[mid] ==
 key)
             
return
 mid;
          
else if (indx[mid] <
 key)
                  l 
= mid + 1
;
              
else r =
 mid;
    }
}

void
 Init_Index()
{
     sort(indx
+1,indx+1+
cntx);
   
//
  for (int i = 1; i <= cntx; i++)
  
//       printf("%d,",indx[i]);

     int m = 1
     
for (int i = 2; i <= cntx; i++
)
     {
         
         
if (indx[i] != indx[i-1
])
         {
            m
++
;
            indx[m] 
=
 indx[i];
         }
     }
         
     cntx 
=
 m;
}

int
 main()
{
    
int
 n,i,j,k,id;
    
int count[15010
];
    
while (scanf("%d",&n) !=
 EOF)
    {
          
for (i = 1; i <= n; i++
)
          {
              count[i] 
= 0
;
              scanf(
"%d %d",&x[i],&
y[i]);
              indx[i] 
=
 x[i];
          }
         
//
 for (i = 1; i <= n ;i++)
        
//
      printf("%d ",indx[i]);
        
//  printf("\n");

          cntx = n; 
          Init_Index();
       
/*
   for (i = 1; i <= cntx; i++)
              printf("%d ",indx[i]);
           printf("cntx = %d\n",cntx);
*/

          cnt 
= 0;
          Creat(root,
1
,cntx);
          
for (i = 1; i <= n; i++
)
          {
              id 
=
 Bi_Search(x[i]);
            
//  printf("id = %d\n",id);

              k = query(root,1,id);
            
//  printf("i = %d,k = %d\n",i,k);

              count[k] ++;
              Insert(root,id);
          }
          
for (i = 0; i < n; i++
)
              printf(
"%d\n"
,count[i]);
          
    }
    
return 0
;
}



树状数组的cpp代码:

#include<stdio.h>
int a[32002];
int level[15000
];
int
 N;
int lowbit(int
 n){
    
return n&(-
n);
}
int Sum(int
 n)
{
    
int result = 0
;
    
while(n!=0
){
        result
+=
a[n];
        n
-=
lowbit(n);
    }
    
return
 result;
}
void Update(int
 n)
{
    
while(n<=32001
){
        a[n]
++
;
        n
+=
lowbit(n);
    }
}
void
 init()
{
    
int
 i;
    
for(i=0;i<=N;i++
)
        level[i]
=a[i]=0
;
}
int
 main()
{
    
int
 x,y,i;
    scanf(
"%d",&
N);
    i
=
N;
    init();
    
while(i--
){
        scanf(
"%d %d",&x,&
y);
        level[Sum(x
+1)]++
;
        Update(x
+1
);
        
    }

    
for(i=0;i<N;i++
)
        printf(
"%d\n"
,level[i]);
}

posted @ 2010-10-29 14:12 acronix 阅读(146) | 评论 (0)编辑 收藏


题意就不多说了。

分析:就是把poj1177简单改动就行了。

总结:出错时输出看看prelen对不对就行了。




#include <cstdio>
#include 
<stdlib.h>
#include 
<algorithm>
using namespace std;

const int root = 0
;

struct
 Node{
       
int
 l,r,cover;
       
int
 cnt,len;
       
int
 lf,rf;
       
int
 lnd,rnd;
}node[
200010
];
int
 cnt,cnty;
int indx[80010
];

struct
 Line{
       
int
 x,y1,y2;
       
bool
 f;
} line[
80010
];

void Creat(int p ,int l,int
 r)
{
     node[p].l 
= l; node[p].r =
 r;
     node[p].len 
= node[p].cnt = node[p].cover = 0
;
     node[p].lf 
= node[p].rf = 0
;
     
if(r - l > 1
)
     {
          
int mid = (l + r) >> 1
;
          node[p].lnd 
= ++
cnt;
          Creat(cnt,l,mid);
          node[p].rnd 
= ++
cnt;
          Creat(cnt,mid,r);
     }
     
else {node[p].lnd = -1; node[p].rnd = -1
;}
}

void upData(int
 p)
{
     
if (node[p].cover > 0
)
     {
         node[p].len 
= indx[node[p].r] -
 indx[node[p].l];
         node[p].cnt 
= 1
;
         node[p].lf 
= node[p].rf = 1
;
     }
     
else if (node[p].l == node[p].r -1
)
          {
             node[p].cover 
= 0
;
             node[p].len 
= 0
;
             node[p].lf 
= node[p].rf = node[p].cnt = 0
;
          }
          
else
 {
                
int left =
 node[p].lnd;
                
int right =
 node[p].rnd;
                node[p].len 
= node[left].len +
 node[right].len;
                node[p].lf 
=
 node[left].lf;
                node[p].rf 
=
 node[right].rf;
                node[p].cnt 
= node[left].cnt + node[right].cnt - node[left].rf*
node[right].lf;
               }
}

void Insert(int p,int l,int
 r)
{
     
if(l <= node[p].l && node[p].r <=
 r)
          node[p].cover 
++
;
     
else
 {
            
int mid = (node[p].l + node[p].r) >> 1
;
            
if(mid >
 l)
                   Insert(node[p].lnd,l,r);
            
if (mid <
 r)
               Insert(node[p].rnd,l,r);
          }
     upData(p);
}

void Delete(int p,int l,int
 r)
{
     
if(l <= node[p].l && node[p].r <=
 r)
          node[p].cover
--
;
     
else
 {
             
int mid = (node[p].l + node[p].r) >> 1
;
             
if(mid >
 l)
                    Delete(node[p].lnd,l,r);
             
if (mid <
 r)
                Delete(node[p].rnd,l,r);
          }
     upData(p);
}

bool cmp(const Line &a,const Line &
b)
{
    
return a.x <
 b.x;
}

int Bi_Search(int key)//二分查找 

{
    
int l = 1,r = cnty+1
,mid;
    
while (l <
 r)
    {
          mid 
= (l + r) >> 1
;
          
if(indx[mid] ==
 key)
              
return
 mid;
          
else if(indx[mid] <
 key)
                  l  
= mid + 1
;
               
else r =
 mid; 
    }
}

void Init_Index()//离散化(排序= 去重 

{
    sort(indx
+1,indx+1+
cnty);
    
int m = 1
;
    
for (int i = 2; i <= cnty; i++
)
        
if(indx[i] != indx[i-1
])
        {
           m
++
;
           indx[m] 
=
 indx[i];
        }
    cnty 
=
 m;
}

int
 main()
{
    
int
 n,i,j;
    
long long
 ans;
    
int
 x,y,h,prelen,left,right;
    
while (scanf("%d",&n) !=
 EOF)
    {
          cnty 
= 1
;
          indx[cnty] 
= 0
;
          
for (i = 1; i <= n+n; i+=2
)
          {
              scanf(
"%d %d %d",&x,&y,&
h);
              line[i].x 
= x; line[i].y1 = 0; line[i].y2 =
 h; 
              line[i].f 
= true
;
              line[i
+1].x = y; line[i+1].y1= 0; line[i+1].y2 =
 h; 
              line[i
+1].f = false
;
              indx[
++cnty] =
 h;
          }
          sort(line
+1,line+1+n+
n,cmp);
          Init_Index();
          cnt 
= 0
;
          Creat(root,
1
,cnty);
          left 
= 1
;
          right 
= Bi_Search(line[1
].y2);
          Insert(root,left,right);
          prelen 
=
 node[root].len;
          ans 
= 0
;
          
//printf("1.len = %d\n",prelen);

          for (i = 2; i <= n+n; i++)
          {
              left  
= 1
;
              right 
=
 Bi_Search(line[i].y2);
              
              
if
 (line[i].f)
                 Insert(root,left,right);
              
else
 Delete(root,left,right);
              
              
//注意 long long 

              ans += (long long)prelen*((long long)line[i].x - (long long)line[i-1].x);
              prelen 
=
 node[root].len; 
              
/****************检查出错很好的手段************************/

              
//printf("i = %d.len = %d\n",i,prelen); 
          }
          printf(
"%I64d\n"
,ans);
    }
    
return 0
;
}

posted @ 2010-10-29 14:01 acronix 阅读(217) | 评论 (0)编辑 收藏