C++博客-acronix

poj3301（三分）

acronix — Sat, 13 Nov 2010 13:35:00 GMT

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

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

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

附上我的程序：

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

const int maxn = 10010;
const double eps = 1e-8;
double a[maxn],b[maxn],c[maxn];
int n;

double cal(double x)
{
    double s = -1e100,tmp;//注意s的要尽量小
    for (int i = 1; i <= n; i++)
    {
        tmp = a[i]*x*x + b[i]*x + c[i];
        s = max(tmp,s);
    }
    return s;
}

void solve()
{
    double left = 0.0, right = 1000.0;
    double mid, midmid;
    double mid_v, midmid_v;
    while (left + eps < right)
    {
        mid = (left + right) / 2;
        midmid = (mid + right) / 2;
        mid_v = cal(mid);
        midmid_v = cal(midmid);
        if (mid_v < midmid_v)
            right = midmid;
        else left = mid;
    }
    printf("%.4lf\n",cal((left+right)/2));
}

int main()
{
    int t,i,j;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&n);
        for (i = 1; i <= n; i++)
            scanf("%lf %lf %lf",&a[i],&b[i],&c[i]);
        solve();
    }
    return 0;
}

某某程序：

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 10086;
double a[MAXN], b[MAXN], c[MAXN];

int main() {
    int re, n;
    double l, r, m1, m2, y1, y2;

    scanf("%d", &re);
    for (int ri = 1; ri <= re; ++ri) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%lf%lf%lf", &a[i], &b[i], &c[i]);
        }
        l = 0;
        r = 1000;
        while (r - l > 1e-8) {
            m1 = (l * 2 + r) / 3;
            m2 = (l + r * 2) / 3;
            y1 = y2 = -1e100;
            for (int i = 0; i < n; ++i) {
                y1 = max(y1, (a[i] * m1 + b[i]) * m1 + c[i]);
                y2 = max(y2, (a[i] * m2 + b[i]) * m2 + c[i]);
            }
            if (y1 < y2) {
                r = m2;
            } else {
                l = m1;
            }
        }
        l = (l + r) / 2;
        r = -1e100;
        for (int i = 0; i < n; ++i) {
            r = max(r, (a[i] * l + b[i]) * l + c[i]);
        }
        printf("%.4lf\n", r);
    }

    return 0;
}

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

模版化：

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;
}

acronix 2010-11-13 21:35 发表评论

poj3294(后缀数组，dc3)

acronix — Fri, 12 Nov 2010 16:09:00 GMT

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

acronix 2010-11-13 00:09 发表评论

poj3264(自写rmq模板)

acronix — Fri, 05 Nov 2010 15:41:00 GMT

//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;
}

acronix 2010-11-05 23:41 发表评论

poj3067Japan（树状数组求逆序对）

acronix — Fri, 29 Oct 2010 07:23:00 GMT

题意：自己看吧。

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

注意：边可以达到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;
}

acronix 2010-10-29 15:23 发表评论

poj2481cows（树状数组）

acronix — Fri, 29 Oct 2010 07:18:00 GMT

题意：给每只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;
}

acronix 2010-10-29 15:18 发表评论

poj1195Mobile phones（二维树状数组）

acronix — Fri, 29 Oct 2010 07:05:00 GMT

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

分析：就是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;
}

acronix 2010-10-29 15:05 发表评论

pojMatrix 树状数组必做题目

acronix — Fri, 29 Oct 2010 06:58:00 GMT

题意：自己看吧。

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

            首先这里我不具体解释 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;
}

acronix 2010-10-29 14:58 发表评论

poj1151 Atlantis 标准的矩阵面积并

acronix — Fri, 29 Oct 2010 06:17:00 GMT

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

#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;
}

acronix 2010-10-29 14:17 发表评论

poj2352stars 点线段树和树状数组

acronix — Fri, 29 Oct 2010 06:12:00 GMT

题意：给星星的坐标，定义每个星星左下角（包括正左边和正上方）的星星数是它的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]);
}

acronix 2010-10-29 14:12 发表评论

poj3277City Horizon线段树求矩阵面积并

acronix — Fri, 29 Oct 2010 06:01:00 GMT

题意就不多说了。

分析：就是把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;
}

acronix 2010-10-29 14:01 发表评论