POJ 3468

题目地址:http://poj.org/problem?id=3468

题目大意

给定一个数列$A_1, A_2, \cdots, A_N$以及$Q$个操作,按顺序执行这些操作,操作分两种:

  • 给出$l, r, x$,对$A_l, A_{l+1}, \cdots, A_r$同时加上$x$
  • 给出$l, r$,求$A_l, A_{l+1}, \cdots, A_r$的和。

思路

这题前面有用线段树的方法:【线段树】POJ 2991 3468 HDOJ 1166 1754

用树状数组比较简单,树状数组可以快速求和$\sum_{i=1}^j A_i$和更新数据。

考虑用两个树状数组bit0bit1,分别维护$\sum_{i=1}^j A_i$和增量。

当加上$x$前,$s(i) = \sum_{i=1}^j A_i$,加上$x$后,有:

  1. $i<l \to s’(i) = s(i)$
  2. $l\leq i\leq r\to s’(i) = s(i) + x\times (i-l+1) = s(i) - x\times (l-1) + x\times i$
  3. $i < r \to s’(i) = s(i) + x\times (r-l+1) = s(i) + x\times r - x\times(l-1)$

所以,令$s’(i) = sum(bit0, i) + sum(bit1, i)\times i$,则在区间$[l, r]$加上$x$相当于:

  • bit0l位置上-x(l-1)
  • bit1l位置上+x
  • bit0r位置上+rx
  • bit1r位置上-x

那么查询的时候,结果为$s'(r) - s'(l-1)$

AC代码

/*************************************************************************
    > File Name: 3468_3.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-24 日 11:12:19 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 100000+5;
typedef long long ll;
int A[MAXN];
ll bit0[MAXN], bit1[MAXN];
int N, Q;

void add(ll *bit, int i, int x) {
    while(i<=N) {
        bit[i] += x;
        i += i&-i;
    }
}

ll sum(ll *bit, int i) {
    ll res = 0;
    while(i) {
        res += bit[i];
        i -= i&-i;
    }
    return res;
}

void solve() {
    for (int i = 1; i <= N; ++i) add(bit0, i, A[i]);
    char op;
    int a, b, c;
    for (int i = 0; i < Q; ++i) {
        getchar();
        scanf("%c%d%d", &op, &a, &b);
        if(op == 'C') { // [a,b]区间+c
            scanf("%d", &c);
            add(bit0, a, -c*(a-1));
            add(bit1, a, c); // c*a-c*(a-1) = +c
            add(bit0, b, c*b);
            add(bit1, b, -c);
        }
        else {
            ll ans = (sum(bit0, b) + b*sum(bit1, b)) - (sum(bit0, a-1) + (a-1)*sum(bit1, a-1));
            printf("%lld\n", ans);
        }
    }

}

int main() {
#ifdef Oj
    freopen("3468.in", "r", stdin);
    // freopen("3468_3.out", "w",stdout);
#endif
    scanf("%d%d", &N, &Q);
    for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
    solve();
    return 0;
}

POJ 1990

题目地址:http://poj.org/problem?id=1990

题目大意

有$N$头牛排成一排,每头牛有两个属性:听力$v$和坐标$x$。若两头牛$i,j$能正常交流的话需要$max(v_i, v_j) |x_i-x_j|$的音量,求所有牛交流时的音量和。

思路

这题其实就是求$\sum_{i, j\in S, i\neq j}max(v_i, v_j)d_{ij}$,若直接求的话需要$O(N^2)$的复杂度肯定超时。

然后可以这么想,按照$v$值从小到大排序,每次处理的牛都是当前$v$最大的,然后乘上前面的牛的距离$d$即可。

这里距离计算需要用到两个树状数组cntX,下标即坐标,分别维护当前牛(坐标x)的前面牛的数量和坐标,那么

  • lcnt = sum(cnt, x)表示当前牛左边的牛的数量
  • rcnt = sum(cnt, MAXN) - sum(cnt, x)表示当前牛右边的牛的数量
  • lx = sum(X, x)表示当前牛左边的牛的坐标累计和
  • rx = sum(X, MAXX) - sum(X, x)表示当前牛右边的牛的坐标累计和

则距离$d = lcnt\times x - lx + rx - rcnt\times x$

每次处理完一头牛后,对cnt进行标记,X记录牛的坐标。

AC代码

/*************************************************************************
    > File Name: 1990.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-24 日 18:35:43 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 20000+5;
typedef long long ll;
int N;
pair<int, int> cows[MAXN]; // first:v, second:x
ll cnt[MAXN], X[MAXN]; // 下标为坐标,分别维护牛左右两边的数量和坐标。

void add(ll *bit, int i, int x) {
    while(i<=MAXN) {
        bit[i] += x;
        i += i&-i;
    }
}
ll sum(ll *bit, int i) {
    ll res = 0;
    while(i > 0) {
        res += bit[i];
        i -= i&-i;
    }
    return res;
}

void solve() {
    sort(cows, cows+N, less<pair<int,int> >()); // 按照v从小到大的顺序处理,这样每次的v就是最大的了。
    ll ans = 0;
    for(int i=0; i<N; ++i) {
        int v = cows[i].first, x = cows[i].second; // 从第一头牛开始处理
        int lcnt = sum(cnt, x); // 左边[1, x]范围内的牛的数量
        int rcnt = sum(cnt, MAXN-1) - lcnt; // 右边(x, MAXN)范围的牛的数量
        ll lx = sum(X, x); // 左边[1,x]范围的牛的累计坐标
        ll rx = sum(X, MAXN-1) - lx; // 右边(x, MAXN)范围的牛的累计坐标
        // printf("lcnt:%d rcnt:%d lx:%lld rx:%lld v:%d x:%d ", lcnt, rcnt, lx, rx, v, x);
        // printf("lxs:%lld rxx:%lld\n", x*lcnt - lx, rx - x*rcnt);
        ans += v*(x*lcnt - lx + rx - x*rcnt);
        add(cnt, x, 1); // 标记当前牛,以计数用
        add(X, x, x); // 标记当前牛位置,统计距离用
    }
    cout << ans << endl;
}

int main() {
#ifdef Oj
    freopen("1990.in", "r", stdin);
    // freopen("1990.out", "w",stdout);
#endif
    cin.sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> cows[i].first >> cows[i].second; //v, x
    solve();
    return 0;
}

POJ 3109

题目地址:http://poj.org/problem?id=3109

题目大意

在一个棋盘上有些黑点,若白点的上下左右都有黑点的话,那么它就会变黑。给定一个棋盘状态(已知某些黑点坐标),问最后一共会有多少个黑点。

思路

扫描线+树状数组。

首先坐标范围比较大,需要离散化(即压缩),然后y从小到大扫描,并用树状数组维护黑点间可能变黑的数量。

AC代码

/*************************************************************************
    > File Name: 3109.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-26 二 16:34:56 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 100000+30;
typedef long long ll;

int N;
int x[MAXN], y[MAXN];
bool visited[MAXN]; // 标记x坐标是否访问过,访问过的话再次访问说明同x坐标。

ll bit0[MAXN], bit1[MAXN]; // 负责维护原始值和增量的树状数组,用来记录区间内黑点数量。

// 树状数组部分
void add(ll *bit, int i, ll x) {
    while(i<=MAXN) {
        bit[i] += x;
        i += i&-i;
    }
}

ll sum(ll *bit, int i) {
    ll res = 0;
    while(i>0) {
        res += bit[i];
        i -= i&-i;
    }
    return res;
}

// 区间和,更新区间值[l, r]
ll getsum(int i) {
    return sum(bit0, i) + sum(bit1, i)*i;
}


void update(int l, int r, int x) {
    add(bit0, l, -x*(l-1));
    add(bit1, l, x);
    add(bit1, r, -x);
    add(bit0, r, r*x);
}

// 坐标离散化
int compress(int *x) {
    vector<int> xs;
    for (int i = 0; i < N; ++i)
        xs.push_back(x[i]);
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    for (int i = 0; i < N; ++i)
        x[i] = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin() + 1;
    return xs.size();
}


void solve() {
    compress(x); // 离散化
    int h = compress(y);
    vector<int> line[MAXN];
    for(int i=0; i<N; ++i) line[y[i]].push_back(x[i]);
    ll ans = N;
    for(int y=1; y<=h; ++y) {
        vector<int> &xs = line[y];
        sort(xs.begin(), xs.end());
        for(vector<int>::iterator i = xs.begin(); i!=xs.end(); ++i) { // 从左往右遍历每个黑点
            int X = *i;
            ll s = getsum(X) - getsum(X-1); // 当前坐标的黑点数
            if(visited[X]) ans += s; // 前面已经标记过x轴的话
            visited[X] = true;
            update(X, X, -s); // 归零
            if(i+1 < xs.end() && X+1 <= (*(i+1)-1)) update(X+1, *(i+1)-1, 1); // 标记两个相邻黑点间的黑点数
        }
    }
    printf("%lld\n", ans);
}

int main() {
#ifdef Oj
    freopen("3109.in", "r", stdin);
    // freopen("3109.out", "w",stdout);
#endif
    // cin >> N;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) scanf("%d%d", x+i, y+i);
    solve();
    return 0;
}

POJ 2155

题目地址:http://poj.org/problem?id=2155

题目大意

在一个元素值为0或1的$N\times N$阶矩阵$A$,执行$T$组操作,操作有两种:

  • 将矩形区域$(x_1, y_1):(x_2, y_2)$的所有值反转
  • 问$A_{ij}$的值为多少。

思路

刚开始用的是二维树状数组,每维y维护一个x轴树状数组,更新的时候遍历y,并根据前面介绍的方法更新区间x(所有元素+1),维护的时候也是遍历y,求出区间x的和(mod2)就是答案,超时了。。。

看了下题解,也是二维树状数组,树状数组可以快速更新某个元素的值,那么约定更新$A_{ij}$(+1)这个值就是更新区域$(i, j):(N, N)$(因为树状数组更新操作是往后更新的),那么更新区域操作相当于更新四个点:

  1. update(x1, y1)
  2. update(x2+1, y2+1)
  3. update(x1, y2+1)
  4. update(x2+1, y1)

而查询某个点的值$A_{ij}$,直接求出这个点的和(mod 2)即可(求和是往前,这里的和相当于区域$(1,1):(i,j)$的操作次数。)

AC代码

/*************************************************************************
    > File Name: 2155_2.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-27 三 15:11:55 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int bit[1000+5][1000+5];
int N,T;

void update(int x, int y) {
    for(int i=x; i<=N; i+=i&-i)
        for (int j = y; j <= N; j+=j&-j) bit[i][j]++;
}
int get(int x, int y) {
    int res = 0;
    for(int i=x; i>0; i-=i&-i)
        for (int j=y; j > 0; j-=j&-j) res += bit[i][j];
    return res;
}

void solve() {
    memset(bit, 0, sizeof(bit));
    char op;
    int x1, y1, x2, y2;
    while(T--) {
        getchar();
        scanf("%c", &op);
        if(op == 'C') {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            update(x2+1, y2+1); // 更新一个点相当于更新一个区域(这点到矩阵右下角操作数+1)
            update(x1, y1);
            update(x1, y2+1);
            update(x2+1, y1);
        }
        else {
            scanf("%d%d", &x1, &y1);
            printf("%d\n", get(x1, y1)%2); // 求和相当于一个区域的操作总数(矩阵左上角到这点)
        }
    }

}

int main() {
#ifdef Oj
    freopen("2155.in", "r", stdin);
    // freopen("2155_2.out", "w",stdout);
#endif
    int X;
    scanf("%d", &X);
    while(X--) {
        scanf("%d%d", &N, &T);
        solve();
        printf("\n");
    }
    return 0;
}

POJ 2886

题目地址:http://poj.org/problem?id=2886

题目大意

N个孩子围成一个圈,从第K个开始淘汰,每淘汰一个,出示手中的数字,决定下一个淘汰者,正数表示左手第n个,负数反之。每个人可以拿到的存活回数的因数个数的糖果,求拿到最多糖果数的孩子的名字以及糖果数。

思路

http://www.hankcs.com/program/algorithm/poj-2886-who-gets-the-most-candies.html

第一步需要做一份因式分解表,table[i]=x表示i有x个因数。怎么求一个数有多少个约数呢?先将x分解为质因数之积,比如$270 = 3 \times 3 \times 3 \times 2 \times 5$,那么分别从所有{质因数的n次方}中分别挑一个出来累乘就可以得出一个唯一的因数。

比如$\lbrace 1, 3, 9, 27\rbrace \times \lbrace1, 2\rbrace \times \lbrace1, 5\rbrace$,这三个集合中每个集合挑一个数出来做乘法,一共有$4 \times 2 \times 2 = 16$种,于是因数有16个。

然后需要在剔除人之后还能快速将一个人的当前的次序与最初的次序联系起来,朴素的做法每淘汰一个人就更新前面的每个人的次序是非常耗时的,这种区域修改可以活用BIT高效完成。

BIT用来维护初始下标,BIT将一个人当前的次序与最初的次序关联起来,具体来说:

用BIT的sum(x)的值表示目前剩下的第几人(x表示初始下标,当然随着逐渐淘汰,有些x代入sum(x)没有实际的意义),每淘汰一个人(初始id=x),就add(x, -1)。如何快速知道第sum的家伙以前的下标是多少呢?可以用二分,因为前缀和必定是单调递增的。

举个例子说明问题,假设有6人参加,BIT的前缀和初始为

123456

后来淘汰了下标为2的人,BIT的前缀和变为

112345

对应人的编号为

13456

这时我们想知道剩下的人中第3个人的初始下标(13456的第3个数是4),我们从前缀和里面找,发现sum(4)=3,那么第3个人的初始下标就是4。

AC代码

/*************************************************************************
    > File Name: 2886.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-29 五 10:31:27 CST
 ************************************************************************/

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

const int MAXN = 500000 + 5;
int factors[MAXN];
int N, K;
int bit[MAXN]; // 维护下标

struct Kid{
    char name[15];
    int card;
} kid[MAXN];

void init_factors() { // 预处理因子数
    fill(factors+1, factors+MAXN, 1);
    for(int i=2; i<MAXN; ++i)
        if(factors[i] == 1)
            for(int j=i; j<MAXN; j+=i) {
                int k = 0;
                for(int m=j; m % i == 0; m/=i, ++k);
                factors[j] *= k+1; // 加上1
            }
}

void add(int i, int x) {
    while(i <= N) {
        bit[i] += x;
        i+=i&-i;
    }
}

int sum(int i) {
    int res = 0;
    while(i>0) {
        res += bit[i];
        i-=i&-i;
    }
    return res;
}

int find(int x) { // 找出下标为x的小孩的编号
    int lb = 0, ub = N;
    while(ub - lb > 1) { // (lb, ub]
        int mid = (ub + lb) >> 1;
        if(sum(mid) >= x) ub = mid;
        else lb = mid;
    }
    return ub;
}

void solve() {
    int cnt = N, cur = K, curi = K; // 圈圈中剩余的孩子数量cnt,当前孩子编号cur,当前孩子下标curi
    int maxi = 0, maxf = 0;

    while(cnt > 1) {
        // printf("cur: %d", cur);
        if(factors[N-cnt+1] > maxf) {
            maxf = factors[N-cnt+1];
            maxi = cur;
        }
        add(cur, -1); // 当前孩子出队
        --cnt; // 剩余数少一
        if(kid[cur].card > 0) // 求出下一个出队的孩子的下标
            curi = (curi - 1 + kid[cur].card) % cnt;
        else
            curi = ((curi + kid[cur].card) % cnt + cnt) % cnt;
        if(curi == 0) curi = cnt;
        // printf(" curi: %d\n", curi);
        cur = find(curi); // 求出编号
    }
    // printf("cur: %d\n", cur);

    // 检查最后一个出队的孩子
    if(factors[N-cnt+1] > maxf) {
        maxf = factors[N-cnt+1];
        maxi = cur;
    }

    printf("%s %d\n", kid[maxi].name, maxf);
}

int main() {
#ifdef Oj
    freopen("2886.in", "r", stdin);
    // freopen("2886.out", "w",stdout);
#endif
    init_factors();
    while(scanf("%d%d", &N, &K) == 2) {
        memset(bit, 0, sizeof(bit));
        for(int i=1; i<=N; ++i) {
            scanf("%s%d", kid[i].name, &kid[i].card);
            add(i, 1);
        }
        solve();
    }
    return 0;
}

POJ 1201

题目地址:http://poj.org/problem?id=1201

题目大意

给出$n$个闭区间$[a, b]$和在该区间内挑$c$个数,使得挑选出来的数集合最小有多大?。

思路

贪心+树状数组,区间按照b升序,然后从每个区间尾部选数,然后标记。

AC代码

/*************************************************************************
    > File Name: 1201.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-31 日 21:33:21 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 50000+5;
struct Dat{
    int a, b, c;
    bool operator<(const Dat &B) const {
        return b < B.b;
    }
} dat[MAXN];
int N;
int bit[MAXN];
bool used[MAXN];

void add(int i, int x) {
    while(i <= MAXN) {
        bit[i] += x;
        i += i&-i;
    }
}

int sum(int i) {
    int res = 0;
    while(i > 0) {
        res += bit[i];
        i -= i&-i;
    }
    return res;
}

void solve() {
    sort(dat, dat+N);
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        // printf("[%d, %d] %d\n", dat[i].a, dat[i].b, dat[i].c);
        int c = sum(dat[i].b) - sum(dat[i].a-1); // 该区间已经选择的数的个数
        if(c < dat[i].c) {
            // printf("remain: %d have: %d\n", dat[i].c-c, c);
            ans += dat[i].c - c; // 补上
            int s = dat[i].b; // 从尾部开始选
            while(c < dat[i].c) {
                if(!used[s]) { // 没选过
                    // printf("%d ", s);
                    used[s] = true; // 标记
                    add(s, 1);
                    c++;
                }
                --s;
            }
            // printf("\n");
        }
    }
    printf("%d\n", ans);
}

int main() {
#ifdef Oj
    freopen("1201.in", "r", stdin);
    // freopen("1201.out", "w",stdout);
#endif
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) scanf("%d%d%d", &dat[i].a, &dat[i].b, &dat[i].c);
    solve();
    return 0;
}