C++博客-purplest

ZOJ 3707 Calculate Prime S

purplest — Wed, 24 Jul 2013 07:17:00 GMT

题意：定义了S[n]为{1,2,...,n}的非连续数字的子集的个数，然后对于每个S[n]，如果对于每个1<=i=第k个素的S。然后输出(S[n]/x)%m。

首先证明几个结论。

I. gcd(ab,c)=gcd(a,c) 当gcd(b,c)=1时。
证明：gcd(ab,c)=gcd(a,c)*gcd(b,c)=gcd(a,c)

II. gcd(a,b)=gcd(b, a%b)。
证明：假设a>=b，则a=nb+m。假设g|a，g|b，所以g|(nb+m)，所以g|m。因为a%b=(nb+m)%b=m，所以得证。

III. gcd(fib(i),fib(i+1))=1。
证明：因为fib(i+1)=fib(i)+fib(i-1)，
所以gcd(fib(i),fib(i+1))=gcd(fib(i),fib(i)+fib(i-1))=gcd(fib(i),(fib(i)+fib(i-1))%fib(i))=gcd(fib(i),gcd(fib-1))，
可以把euclid的过程给展开，得到：
fib(i+1)=1*fib(i)+fib(i-1)
fib(i)=1*fib(i-1)+fib(i-2)
fib(i-1)=1*fib(i-2)+fib(i-3)
......
fib(4)=1*fib(3)+fib(2)
fib(3)=2*fib(2)+0
最后一行写出来就是：
2 = 2*1+0
所以gcd(fib(i),fib(i+1))=fib(2)=1;
英文原文证明以及反证法参考：

Consecutive Fibonacci Numbers Relatively Prime

http://mathforum.org/library/drmath/view/52716.html

IV. fib(u+v)=fib(u)fib(v-1)+fib(u+1)fib(v).
证明：利用反证法。
当u=1时：fib(1+v)=fib(1)fib(v-1)+fib(2)fib(v)=fib(v-1)+fib(v) 成立。
假设u=n时成立：fib(n+v)=fib(n)fib(v-1)+fib(n+1)fib(v) 成立。
u=n+1时：
fib(n+1+v)=fib(n+v)+fib(n+v-1)=fib(n)fib(v-1)+fib(n+1)fib(v) + fib(n-1)fib(v-1)+fib(n)fib(v)
=fib(v-1)(fib(n)+fib(n-1)) + fib(v)(fib(n-1)+fib(n)) = fib(n+1)fib(v-1)+fib(n+2)fib(v) = fib(n+1+v)
所以，由数学归纳法可以得证。
英文原文证明以及Binet Formula证明参考：
http://mathforum.org/library/drmath/view/51624.html

V. fibonacci-gcd proof: gcd(fib(n),fib(m))=fib(gcd(n,m)).
证明：假设n<=m，则: gcd(fib(n),fib(m))=gcd(fib(n),fib(n+k))，由证明IV，可得：
gcd(fib(n),fib(n+k))=gcd(fib(n),fib(n)fib(k-1)+fib(n+1)fib(k))
=gcd(fib(n),(fib(n)fib(k-1)+fib(n+1)fib(k))%fbi(b))
=gcd(fib(n),fib(n+1)fib(k))，由证明III，gcd(fib(b),fib(n+1))=1，所以由证明I可得：
gcd(fib(n),fib(n+1)fib(k))=gcd(fib(n),fib(k))，所以可得：
gcd(fib(n),fib(m))=gcd(fib(n),fib(m%n))。由展开euclid算法可知，算法在gcd(fib(g),fib(0))时停止，而g=gcd(m,n)。
所以由euclid算法的定义可得gcd(fib(g),fib(0))=fib(g)。
所以得证gcd(fib(n),fib(m))=fib(gcd(n,m))
英文原文证明参考：
http://mathforum.org/library/drmath/view/61690.html

VI. (a/b)%c=(a%bc)/b 当 b|a。
证明：因为b|a，所以a=kb。
左边=(a/b)%c=(kb/b)%c=k%c。
右边=(kb%bc)/b=((k%c)b)/b=k%c。
所以得证。

VII. fibonacci的一个结论：

矩阵快速幂即可。

VIII. 又一个结论，因为x很小（x<=100），所以能在题目给定的时间内枚举到所需的S[n]。

至此，此题需要的证明已齐，只需要素数筛法预处理出所有的位数，然后再暴力枚举即可。

#include
#include
#include
#define LL long long
using namespace std;

const int N = 15486042;
int MOD;
int prime[1001000], top;
bool isnot[20010000];
int ncase;
int k, x, m;
LL now, next;

struct Matrix
{
    LL ma[2][2];
    Matrix()
    {
        ma[0][0]=ma[1][1]=1;
        ma[0][1]=ma[1][0]=0;
    }
    void init()
    {
        ma[0][0]=ma[1][0]=ma[0][1]=1;
        ma[1][1]=0;
    }
    Matrix operator * (const Matrix &a) const
    {
        Matrix res;
        for ( int i = 0 ; i < 2 ; i++ )
            for ( int j = 0 ; j < 2 ; j++ )
            {
                res.ma[i][j]=0;
                for ( int k = 0 ; k < 2 ; k++ )
                    res.ma[i][j]=(res.ma[i][j]+ma[i][k]*a.ma[k][j])%MOD;
                res.ma[i][j]%=MOD;
            }
        return res;
    }
};

void init_prime()
{
    memset(isnot,0,sizeof(isnot));
    top = 1;
    for ( int i = 2 ; i < N ; i++ )
        if (!isnot[i])
        {
            prime[top++]=i;
            if (i<10000)
                for ( int j = i+i ; j < N ; j+=i )
                    isnot[j]=1;
        }
    prime[1]=3;prime[2]=4;
}

void init(int k)
{
    Matrix res, a;
    a.init();
    while (k)
    {
        if (k&1)
            res = res*a;
        a=a*a;
        k>>=1;
    }
    next = (res.ma[0][0]+res.ma[1][0])%MOD;
    now = (res.ma[0][1]+res.ma[1][1])%MOD;
}

int main()
{
    init_prime();
    scanf("%d", &ncase);
    while (ncase--)
    {
        scanf("%d%d%d", &k, &x, &m);
        MOD = x*m;
        init(prime[k]);
        while (now%x)
        {
            swap(now,next);
            next = (now+next)%MOD;
        }
        printf("%lld\n", now/x);
    }
    return 0;
}

purplest 2013-07-24 15:17 发表评论

最大连续区间和的算法总结

purplest — Mon, 04 Mar 2013 06:58:00 GMT

最大连续区间和是一个经典的问题。给定一个长度为n的序列a[1],a[2]...a[n-1],a[n]，求一个连续的子序列a[i],a[i+1]...a[j-1],a[j]，使得a[i]+a[i+1]...a[j-1]+a[j]最大。

①最简单最容易想到的就是根据定义来枚举。
枚举上下界{i,j | 0<=i<=j<=n}，维护一个max值即可。
其中枚举上下界的时间复杂度为O(n^2)，求区间和的复杂度为O(n)，所以总时间复杂度为O(n^3)。

for ( int i = 1 ; i <= n ; i++ )
for ( int j = i ; j <= n ; j++ )
ans = max(ans,accumulate(a+i,a+j+1,0));

②其实就是第一种方法的优化。
这里有个很容易想到的优化，即预处理出前缀和sum[i]=a[0]+a[1]+...+a[i-1]+a[i]，算区间和的时候即可将求区间和的复杂度降到O(1)，枚举上下界的复杂度不变，所以总时间复杂度为O(n^2)。

for ( int i = 1 ; i <= n ; i++ )
    sum[i]=sum[i-1]+a[i];
for ( int i = 1 ; i <= n ; i++ )
    for ( int j = i ; j <= n ; j++ )
        ans = max(ans,sum[j]-sum[i-1]);

③可以利用动态规划的思维来继续优化，得到一个线性的算法，也是最大连续区间和的标准算法
定义maxn[i]为以i为结尾的最大连续和，则很容易找到递推关系：maxn[i]=max{0,maxn[i-1]}+a[i]。
所以只需要扫描一遍即可，总时间复杂度为O(n)。

for ( int i = 1 ; i <= n ; i++ )
{
last = max(0,last)+a[i];
ans = max(ans,last);
}

④同样用到类似的思维。
首先也需要预处理出前缀和sum[i]，可以推出ans=max{sum[i]-min{sum[j] } | 0<=j 而最小前缀和可以动态维护，所以总时间复杂度为O(n)。

for ( int i = 1 ; i <= n ; i++ )
    sum[i]=sum[i-1]+a[i];
for ( int i = 1 ; i <= n ; i++ )
{
    ans = max(ans,sum[i]-minn);
    minn = min(minn,sum[i]);
}

总结：虽然朴素的O(n^3)和前缀和优化的O(n^2)算法很容易想到，但代码实现却反而比方法三麻烦，第四个方法虽然有和方法三相同的复杂度，但需要一个预处理和多出的O(n)的空间，所以，方法三很好很强大。

purplest 2013-03-04 14:58 发表评论

HDU 4267 A Simple Problem with Integers 2012 ACM/ICPC Asia Regional Changchun Online 1001

purplest — Sun, 09 Sep 2012 13:47:00 GMT

这道题即区间更新，单点查询，所以只需要维护区间的增加量即可。

因为1<=k<=10，所以对于不同的起始区间不同的k，一共有55种情况，所以，用开个55的数组即可维护。

利用ZKW线段树思想，标记永久化，每次查到根就over。。

这题方法很多的说，维护10棵树状数组也行，sqrt(n)的方法也行。。。

不过比赛时没想到怎么解决不同的起始区间的k值，算了下还可能MLE，没敢写。。。郁闷。。

#include
#include
#include
#define L(x) (x<<1)
#define R(x) (x<<1|1)

using namespace std;

int n, q, num;
int add[1<<17][55];
int left[1<<17], right[1<<17];
int arr[50100];

void init()
{
    memset(add,0,sizeof(add));
    for ( int i = 0 ; i < num ; i++ )
        left[i+num]=right[i+num]=i;
    for ( int i = num-1 ; i ; i-- )
    {
        left[i]=left[L(i)];
        right[i]=right[R(i)];
    }
}

void update(int s, int t, int k, int val)
{
    int tag = s%k;
    for ( int i = 1 ; i < k ; i++ )
        tag+=i;
    for ( s=s+num-1, t=t+num+1 ; s^t^1 ; s>>=1, t>>=1 )
    {
        if (~s&1)
            add[s^1][tag]+=val;
        if (t&1)
            add[t^1][tag]+=val;
    }
}

int query(int m)
{
    int ans=0, start=m;
    for ( m+=num ; m ; m>>=1 )
        for ( int k = 1 ; k <= 10 ; k++ )
        {
            int tag=start%k;
            for ( int i = 1 ; i < k ; i++ )
                tag+=i;
            ans+=add[m][tag];
        }
    return ans;
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    while (EOF!=scanf("%d", &n))
    {
        for ( int i = 1; i <= n ; i++ )
            scanf("%d", arr+i);
        scanf("%d", &q);
        int cmd, l,r,k,val;
        for (num=1;num<(n+2);num<<=1);
        init();
        while (q--)
        {
            scanf("%d", &cmd);
            if (1==cmd)
            {
                scanf("%d%d%d%d", &l, &r, &k, &val);
                update(l,r,k,val);
            }
            else if (2==cmd)
            {
                scanf("%d", &k);
                printf("%d\n", arr[k]+query(k));
            }
        }
    }
    return 0;
}

purplest 2012-09-09 21:47 发表评论

HDU 4277 USACO ORZ 2012 ACM/ICPC Asia Regional Changchun Online 1011

purplest — Sat, 08 Sep 2012 12:56:00 GMT

就是给N(N<=15)个线段，用这N个线段组成一个三角形，问能组成多少种三角形。

水题，爆搜即可，时间复杂度3^15。

#include
#include
#include
#include <set>

using namespace std;

int ncase;
int n;
int arr[20];
set<long long>col;

void dfs(int a, int b, int c, int cur)
{
    if (cur==n)
    {
        if (a>b||b>c||a>c) return;
        if (a&&b&&c&&a+b>c)
        {
            long long t = 1000000000000LL*a+1000000LL*b+c;
            col.insert(t);
        }
        return;
    }
    dfs(a+arr[cur],b,c,cur+1);
    dfs(a,b+arr[cur],c,cur+1);
    dfs(a,b,c+arr[cur],cur+1);
}

int main()
{
    while (EOF!=scanf("%d", &ncase))
    {
        while (ncase--)
        {
            col.clear();
            scanf("%d", &n);
            for ( int i = 0 ; i < n ; i++ )
                scanf("%d", arr+i);
            dfs(0,0,0,0);
            printf("%d\n", col.size());
        }
    }
    return 0;
}

purplest 2012-09-08 20:56 发表评论

UVa 297 Quadtrees

purplest — Mon, 19 Mar 2012 09:26:00 GMT

哎，太水了，递归建树写了好久的说，太弱了。。。

就是建个四叉树，然后统计占了多少像素，2Y，第一次犯2数组开小了送了个RE。。。

貌似还可以直接建成满四叉树，不过算晕了，没推出子节点咋算的。。真的太弱了= =

#include <stdio.h>
#include <string.h>

struct Node
{
    int flag, child[4];
};

int ncase, sz, res;
char str1[2000], str2[2000];
Node treea[4500], treeb[4500];

void build(int left, int right, int fa, char *str, Node *tree)
{
    for ( int i = left, k = 0 ; i < right && k < 4 ; i++, k++ )
    {
        int t = sz++;
        if ( str[i] == 'p' )
        {
            int j, times=4;
            for ( j = i+1 ; j < right && times ; j++, times-- )
                if ( str[j] == 'p' )
                    times+=4;
            tree[t].flag = 1;
            tree[fa].child[k]=t;
            build(i+1, j, t, str, tree);
            i = j-1;
        }
        else
        {
            tree[t].flag = str[i] == 'e' ? 2 :3;
            tree[fa].child[k]=t;
        }
    }
}

void init(char *str, Node *tree)
{
    int len = strlen(str);
    sz = 1;
    build(0, len, 1, str, tree);
}

void dfs(Node *tree, int root, int deep)
{
    if (tree[root].flag==2)
        return;
    if (tree[root].flag==3)
    {
        res+=1<<deep;
        return;
    }
    if (tree[root].flag==1)
        for ( int i = 0 ; i < 4 ; i++ )
            dfs(tree, tree[root].child[i], deep-2);
}

void get(int root1, int root2, int deep)
{
    if ( !root1 && !root2 )
        return;
    if (treea[root1].flag==3 || treeb[root2].flag==3)
        res+=1<<deep;
    if (treea[root1].flag==2||treeb[root2].flag==2)
        treea[root1].flag==2 ? dfs(treea, root1, deep) : dfs(treeb, root2, deep);
    if (treeb[root2].flag==1&&treea[root1].flag==1)
        for ( int i = 0 ; i < 4 ; i++ )
            get(treea[root1].child[i], treeb[root2].child[i], deep-2);
}

int main()
{
    while ( EOF != scanf("%d", &ncase) )
    {
        memset(treea, 0, sizeof(treea));
        memset(treeb, 0, sizeof(treeb));
        scanf("%s %s", str1, str2);
        init(str1, treea);
        init(str2, treeb);
        res = 0;
        get(1,1,10);
        printf("There are %d black pixels.\n", res);
    }
    return 0;
}

purplest 2012-03-19 17:26 发表评论

UVa 548

purplest — Fri, 16 Mar 2012 09:30:00 GMT

题意：给中序，后序，然后还原二叉树，再输出从root到leaf节点中节点和最小的那个leaf

很无语的是用index这个变量，居然被判了个CE。。。

#include <stdio.h>
#include <string.h>

struct Node
{
    int l, r, v;
};

char ch;
int inorder[10100], postorder[10100];
Node node[10100];
int sz, minn, indexn;

void recover(int inl, int inr, int postl, int postr, int &fa)
{
    if ( inr<inl || postr<postl )
        return;
    int p = ++sz;
    fa = sz;
    node[p].v=postorder[postr];
    int k;
    for ( k = inl ; k <= inr && inorder[k]!=postorder[postr] ; k++);
    int len = k-inl;
    recover(inl, k-1, postl, postl+len-1, node[p].l);
    recover(k+1, inr, postl+len, postr-1, node[p].r);
}

void dfs(int p, int num)
{
    if (!node[p].l&&!node[p].r)
    {
        if ( node[p].v+num < minn )
        {
            indexn = node[p].v;
            minn= node[p].v+num;
        }
        else if ( node[p].v+num == minn )
            if ( indexn > node[p].v)
                indexn = node[p].v;
        return;
    }
    node[p].v+=num;
    if (node[p].l)
        dfs(node[p].l, node[p].v);
    if (node[p].r)
        dfs(node[p].r, node[p].v);
}

int main()
{
    while ( EOF != scanf("%d%c", inorder, &ch) )
    {
        indexn = minn = ~1u>>1;
        memset(node, 0, sizeof(node));
        int top;
        for ( top = 1 ; ch != '\n' ; top++ )
            scanf("%d%c", inorder+top, &ch);
        for ( int i = 0 ; i < top ; i++ )
            scanf("%d", postorder+i);
        recover(0, top-1, 0, top-1, node[sz=0].r);
        dfs(1, 0);
        printf("%d\n", indexn);
    }
    return 0;
}

purplest 2012-03-16 17:30 发表评论

UVa 112 poj 1145

purplest — Fri, 16 Mar 2012 07:56:00 GMT

这题WA死了，5Y。。。

开始没想到还有负数的可能，送了2个WA，一次是犯2忘关调试了，还有一次是 0 () 这组数据没处理

好久没写模拟了，太没状态了，哎，还好把代码给压缩到了100以内

附上AC代码~

#include <stdio.h>
#include <string.h>

struct Node
{
    int l, r, v;
};

Node node[101000];
int num, sum;
char str[2048],stack[101000];
bool flag;

void build(int l, int r, int &fa)
{
    if ( r-l == 1 )
    {
        fa = 0;
        return;
    }
    int t = sum++, j;
    fa = t;
    int len = 0, temp = 0, fh = 1, left = l;
    if ( stack[l+1] == '-' )
    {
        fh=-1;
        left++;
    }
    for ( int i = left+1 ; i < r && ('0' <= stack[i] && stack[i] <= '9' ) ; i++, len++ )
        temp=temp*10+stack[i]-'0';
    node[t].v=temp*fh;
    for ( int i = left+2+len , k = 1 ; i < r && k ; i++ )
    {
        if (stack[i]==')')
            k--;
        else if (stack[i]=='(')
            k++;
        if (!k)
            j = i;
    }
    build(left+len+1, j, node[t].l);
    build(j+1, r-1, node[t].r);
}

void dfs(int p, int n)
{
    node[p].v+=n;
    if (node[p].l)
        dfs(node[p].l, node[p].v);
    if (node[p].r)
        dfs(node[p].r, node[p].v);
    if (!node[p].l&&!node[p].r)
        if (node[p].v==num)
            flag = 1;
}

int main()
{
    while ( EOF != scanf("%d", &num) )
    {
        memset(stack, 0, sizeof(stack));
        memset(node, 0, sizeof(node));
        int top = 0, k = 0;
        for ( int i = 0 ; top == 0 || k ; i = 0)
        {
            gets(str);
            for ( int len = strlen(str) ; i < len ; i++ )
            {
                while ( ' ' == str[i] ) i++;
                if ( '(' == str[i] )
                {
                    k++;
                    stack[top++]=str[i];
                }
                else if( ')' == str[i] )
                {
                    k--;
                    stack[top++]=str[i];
                }
                else if (('0' <= str[i] && str[i] <= '9') || ( '-' == str[i] ))
                    stack[top++]=str[i];
            }
        }
        sum = 1;
        flag = 0;
        build(0, top-1, node[0].r);
        if ( top == 2 )
            puts("no");
        else
        {
            dfs(1, 0);
            flag ? puts("yes"): puts("no");
        }
    }
    return 0;
}

purplest 2012-03-16 15:56 发表评论

Greater New York Regional 2009 解题报告

purplest — Fri, 17 Feb 2012 16:59:00 GMT

摘要: 寒假没事的时候看了下，顺手做了。。。果断AK掉了。。。blog在chengdu regional后就一直没更新了，在被补考前憋的头昏脑胀无力吐槽的时候，就当来清清草吧。。。这套水题就懒得每题单独发了。。。 A题 poj 3781 Nth Largest Value 无与伦比的水，1分钟AC不了可以去shi了。。。我直接扫描三次水过。。 Code highli... 阅读全文

purplest 2012-02-18 00:59 发表评论

hdu 4109 Instrction Arrangement

purplest — Mon, 31 Oct 2011 07:58:00 GMT

一道类似拓扑排序的思路了

开始直接裸的拓扑，结果TLE死。。。

想了很久，改了个加上了个记忆化，171ms搞定了。。。

#include <stdio.h>
#include <string.h>

struct P
{
    int hasfa, haschild, flag;
    int child[1010], index[1010];
}data[1010];

int n, m;
int dp[1010];

int max(int a, int b)
{
    return a>b?a:b;
}

int dfs(int i)
{
    if ( dp[i] )
        return dp[i];
    if ( data[i].haschild )
    {
        int maxn= 0;
        for ( int j = 0 ; j < data[i].flag ; j++ )
        {
            int t= dfs(data[i].index[j])+data[i].child[data[i].index[j]];
            maxn= max( maxn , t );
        }
        return dp[i]= maxn;
    }
    else
        return dp[i]=1;
}

int main()
{
    while ( EOF != scanf("%d%d", &n, &m) )
    {
        int i, u, s, t;
        memset(data, 0, sizeof(P)*n);
        memset(dp, 0, sizeof(dp));
        for ( i = 0 ; i < m ; i++ )
        {
            scanf("%d%d%d", &u, &s, &t);
            data[s].hasfa= 1;
            data[u].haschild= 1;
            data[u].child[s]= t;
            data[u].index[data[u].flag++]= s;
        }
        for ( i = 0 ; i < n ; i++ )
        {
            if ( !data[i].hasfa )
                dp[i]=dfs(i);
        }
        int maxn= 0;
        for ( i = 0 ; i < n ; i++ )
            maxn= max(maxn , dp[i]);
        printf("%d\n", maxn);
    }
    return 0;
}

purplest 2011-10-31 15:58 发表评论

poj 1177 Picture

purplest — Wed, 05 Oct 2011 16:14:00 GMT

把矩形求面积做完后就弄这求周长的题了，其实求周长只比求面积多了几个标记而已了，这里的flag判断入边出边的标记比起求面积的代码写的精炼多了，各种小技巧啊~困扰N久不想看的题总算给搞定了~

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

const int N=5100;

struct Node
{
    int l, r, cover, num, len;
    bool leftc, rightc;
}tree[N<<2];

struct Line
{
    int x, y1, y2, flag;
}line[N<<1];

int temp[N<<1], yline[N<<1];
int n;

int cmpt(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int cmpL(const void *a, const void *b)
{
    return (*(Line *)a).x - (*(Line *)b).x;
}

int myabs(int a)
{
    return a>0?a:-a;
}

void build(int l, int r, int p)
{
    tree[p].l= l;
    tree[p].r= r;
    tree[p].cover= 0;
    tree[p].len= 0;
    tree[p].num= 0;
    tree[p].leftc=tree[p].rightc= 0;
    if ( r-l > 1 )
    {
        int mid= l+r >> 1;
        build(l, mid, 2*p);
        build(mid, r, 2*p+1);
    }
}

void update(int p)
{
    if ( tree[p].cover > 0 )
    {
        tree[p].num= tree[p].leftc = tree[p].rightc = 1;
        tree[p].len= yline[tree[p].r] - yline[tree[p].l];
    }
    else if ( tree[p].r - tree[p].l <= 1)
        tree[p].len= tree[p].leftc= tree[p].rightc= tree[p].num= 0;
    else
    {
        tree[p].rightc= tree[(p<<1)+1].rightc;
        tree[p].leftc= tree[p<<1].leftc;
        tree[p].len= tree[p<<1].len+tree[(p<<1)+1].len;
        tree[p].num= tree[p<<1].num+tree[(p<<1)+1].num-tree[(p<<1)+1].leftc*tree[p<<1].rightc;
    }
}

void insert(int l, int r, int p, int flag)
{
    if ( l <= yline[tree[p].l] && yline[tree[p].r] <= r )
    {
        tree[p].cover+=flag;
        update(p);
        return;
    }
    if ( tree[p].r - tree[p].l <= 1 )
        return;
    int mid= tree[p].l+tree[p].r >> 1;
    if ( l <= yline[mid] )
        insert(l, r, p<<1, flag);
    if ( yline[mid] < r )
        insert(l, r, (p<<1)+1, flag);
    update(p);
}

int main()
{
    while ( ~scanf("%d", &n) )
    {
        int i, m= 0;
        int x1, x2, y1, y2;
        for ( i = 0 ; i < n ; i++ )
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            line[2*i].x= x1;
            line[2*i].y1= y1;
            line[2*i].y2= y2;
            line[2*i].flag= 1;
            line[2*i+1].x= x2;
            line[2*i+1].y1= y1;
            line[2*i+1].y2= y2;
            line[2*i+1].flag= -1;
            temp[2*i]= y1;
            temp[2*i+1]= y2;
        }
        n <<= 1;
        qsort(temp, n, sizeof(int), cmpt);
        qsort(line, n, sizeof(Line), cmpL);
        yline[0]= temp[0];
        for ( i = 1 ; i < n ; i++ )
            if ( yline[m] != temp[i] )
                yline[++m]= temp[i];
        build(0, m, 1);
        int ans, last, lines;
        insert(line[0].y1, line[0].y2, 1, line[0].flag);
        last= ans=tree[1].len;
        lines=tree[1].num;
        for ( i = 1 ; i < n ; i++ )
        {
            insert(line[i].y1, line[i].y2, 1, line[i].flag);
            ans+=2*lines*(line[i].x-line[i-1].x);
            ans+=myabs(tree[1].len-last);
            last= tree[1].len;
            lines=tree[1].num;
        }
        printf("%d\n", ans);
    }
    return 0;
}

purplest 2011-10-06 00:14 发表评论