标签: 离散化

[SDOI2009]虔诚的墓主人 题解

[SDOI2009]虔诚的墓主人 题解

题目地址:洛谷:【P2154】[SDOI2009]虔诚的墓主人 – 洛谷、BZOJ:Problem 1227. — [SDOI2009]虔诚的墓主人

题目描述

小W是一片新造公墓的管理人。公墓可以看成一块N×M的矩形,矩形的每个格点,要么种着一棵常青树,要么是一块还没有归属的墓地。
当地的居民都是非常虔诚的基督徒,他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚,他们希望自己的墓地拥有着较高的虔诚度。
一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地,墓地的正上、正下、正左、正右都有恰好k棵常青树。
小W希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少。

输入输出格式

输入格式:
输入文件religious.in的第一行包含两个用空格分隔的正整数N和M,表示公墓的宽和长,因此这个矩形公墓共有(N+1) ×(M+1)个格点,左下角的坐标为(0, 0),右上角的坐标为(N, M)。
第二行包含一个正整数W,表示公墓中常青树的个数。
第三行起共W行,每行包含两个用空格分隔的非负整数xi和yi,表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。
最后一行包含一个正整数k,意义如题目所示。

输出格式:
输出文件religious.out仅包含一个非负整数,表示这片公墓中所有墓地的虔诚度总和。为了方便起见,答案对2,147,483,648取模。

输入输出样例

输入样例#1:

5 6
13
0 2
0 3
1 2
1 3
2 0
2 1
2 4
2 5
2 6
3 2
3 3
4 3
5 2
2

输出样例#1:

6

说明

图中,以墓地(2, 2)和(2, 3)为中心的十字架各有3个,即它们的虔诚度均为3。其他墓地的虔诚度为0。
对于30%的数据,满足1 ≤ N, M ≤ 1,000。
对于60%的数据,满足1 ≤ N, M ≤ 1,000,000。
对于100%的数据,满足1 ≤ N, M ≤ 1,000,000,000,0 ≤ xi ≤ N,0 ≤ yi ≤ M,1 ≤ W ≤ 100,000,1 ≤ k ≤ 10。
存在50%的数据,满足1 ≤ k ≤ 2。
存在25%的数据,满足1 ≤ W ≤ 10000。

题解

有一些分可以用[eq]O(n^2)[/eq]乱搞过。具体来说就是预处理每个格子上下左右的常青树数量扫一遍格子。N和M太大的时候可以离散化搞一下,容易发现我们的算法其实是[eq]O(w^2)[/eq]的复杂度。
想把[eq]O(n^2)[/eq]搞成[eq]O(n \log n)[/eq]的算法,需要用到数据结构的辅助。假设每个格子上面、下面、左边、右边的常青树数量分别是u、d、l、r,我们发现每个格子对答案的贡献实际上是\mathrm{C}_u^k \times \mathrm{C}_d^k \times \mathrm{C}_l^k \times \mathrm{C}_r^k。如果我们一个格子一个格子地计算,肯定是不行的,考虑用数据结构维护一个维度的信息,这里我们维护的是区间\mathrm{C}_u^k \times \mathrm{C}_d^k的和。可以先把常青树按照坐标双关键字排序。由于每棵常青树只会对它所在行下面的该列格子产生影响,我们可以边处理边更新这个常青树所在列的值。处理同行的每两棵常青树之间的墓区间的上述和,再乘以左右两边常青树的数量即可。这个求前缀和可以使用常数小的树状数组来做。
模数非常特殊,是[eq]2^{31}[/eq],我们可以用unsigned int自然溢出。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>

#include <vector>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 200005;

int n, m, w, k;

unsigned int C[MAXN][15];

inline void calc(int x) {
    C[0][0] = 1;
    for(int i = 1; i <= x; i++) {
        for(int j = 0; j <= std::min(i, k); j++) {
            C[i][j] += C[i - 1][j];
            if(j > 0) C[i][j] += C[i - 1][j - 1];
        }
    }
}

unsigned int tree[MAXN];

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int x, int v) {
    for(int i = x; i <= w; i += lowbit(i)) {
        tree[i] += v;
    }
}

inline unsigned int query(int x) {
    unsigned int res = 0;
    for(int i = x; i; i -= lowbit(i)) {
        res += tree[i];
    }
    return res;
}

struct Tree {
    int x, y;
} trees[MAXN];

inline bool cmp(Tree a, Tree b) {
    return a.x != b.x ? a.x < b.x : a.y < b.y;
}

std::vector<int> tmpx, tmpy;
int rcnt[MAXN], ccnt[MAXN], nrcnt, nccnt[MAXN];

int main() {
    n = readint(); m = readint(); w = readint();
    for(int i = 1; i <= w; i++) {
        trees[i].x = readint(); trees[i].y = readint();
        tmpx.push_back(trees[i].x); tmpy.push_back(trees[i].y);
    }
    k = readint();
    calc(w);
    tmpx.push_back(-1); tmpy.push_back(-1);
    // 离散化
    std::sort(tmpx.begin(), tmpx.end());
    tmpx.erase(std::unique(tmpx.begin(), tmpx.end()), tmpx.end());
    std::sort(tmpy.begin(), tmpy.end());
    tmpy.erase(std::unique(tmpy.begin(), tmpy.end()), tmpy.end());
    for(int i = 1; i <= w; i++) {
        trees[i].x = std::lower_bound(tmpx.begin(), tmpx.end(), trees[i].x) - tmpx.begin();
        trees[i].y = std::lower_bound(tmpy.begin(), tmpy.end(), trees[i].y) - tmpy.begin();
        rcnt[trees[i].x]++; ccnt[trees[i].y]++;
    }
    std::sort(trees + 1, trees + w + 1, cmp);
    unsigned int ans = 0;
    for(int i = 1; i < w; i++) {
        if(trees[i].x != trees[i - 1].x) nrcnt = 0;
        nccnt[trees[i].y]++; nrcnt++;
        // 更新所在列的值
        unsigned int up = nccnt[trees[i].y], down = ccnt[trees[i].y] - nccnt[trees[i].y],
            now = C[up][k] * C[down][k], old = query(trees[i].y) - query(trees[i].y - 1);
        if(now != old) add(trees[i].y, now - old);
        unsigned int left = nrcnt, right = rcnt[trees[i].x] - nrcnt;
        if(trees[i].x != trees[i + 1].x || trees[i + 1].y - trees[i].y <= 1
            || left < k || right < k) continue;
        // 计算两棵常青树之间区间对答案的贡献
        ans += C[left][k] * C[right][k] * (query(trees[i + 1].y - 1) - query(trees[i].y));
    }
    printf("%u", ans % 2147483648u); // 自然溢出是对2^32取模,这里再取一次模
    return 0;
}
[BZOJ3938]Robot 题解

[BZOJ3938]Robot 题解

题目地址:BZOJ:Problem 3938. — Robot

题目描述

小q有n只机器人,一开始他把机器人放在了一条数轴上,第i只机器人在ai的位置上静止,而自己站在原点。在这之后小q会执行一些操作,他想要命令一个机器人向左或者向右移动x格。但是机器人似乎听不清小q的命令,事实上它们会以每秒x格的速度匀速移动。看着自己的机器人越走越远,小q很着急,他想知道当前离他(原点)最远的机器人有多远。具体的操作以及询问见输入格式。注意,不同的机器人之间互不影响,即不用考虑两个机器人撞在了一起的情况。

输入输出格式

输入格式:
共有m个事件,输入将会按事件的时间顺序给出。第一行两个正整数n,m。接下来一行n个整数,第i个数是ai,表示第i个机器人初始的位置(初始移动速度为0)。接下来m行,每行行首是一个非负整数ti,表示该事件点发生的时刻(以秒为单位)。第二个是一个字符串S,代表操作的种类。数字与字符串之间用一个空格隔开。接下来的输入按S的种类分类。若S是command(不带引号),则接下来两个整数ki,xi,表示小q对第ki个机器人执行了操作,该机器人的速度将会被重置,变为向数轴正方向每秒移动xi格(若xi为负数就相当于向数轴负方向每秒移动∣xi∣格)。保证1≤ki≤n。若S是query(不带引号),则你需要输出当前离原点最远的机器人有多远。保证t1≤t2≤t2≤…≤tm。(注:若同一时间发生多次操作,则按读入顺序依次执行)

输出格式:
对于每个query询问,输出一行,包含一个整数表示正确的答案。C/C++输入输出long long时请用%lld。由于本题数据量较大,建议不要使用cin/cout进行输入输出。

输入输出样例

输入样例#1:

4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query

输出样例#1:

180
280

说明

样例说明:
第一个命令执行时,各个机器人的位置为:−20,0,20,100。
第二个命令执行时,各个机器人的位置为:80,0,20,100。
第一个询问时,各个机器人的位置为:180,0,−80,100。
第三个命令执行时,各个机器人的位置为:280,0,−180,100。
第二个询问时,各个机器人的位置为:−20,0,−280,100。

数据范围:
command 的个数为 C,query 的个数为 Q。(所以 C+Q=m)
对于所有的事件满足0 \leq t_i \leq 10^9,对于所有的 command 满足 |x_i| \leq 10^4
对于所有的机器人满足|a_i| \leq 10^9
N, C \leq 10^5
Q \leq 5 \times 10^5

题解

首先考虑机器人的位移-时间图像一定是折线图,我们把折线拆成线段,加入标记永久化线段树里。考虑离线处理需要加入的线段,并且离散化时间。
关于标记永久化线段树存入线段的用法,这个题是一个入门题:[JSOI2008]Blue Mary开公司 题解 | KSkun’s Blog,本题也需要像这个题一样画图来观察直线间的关系,只不过那个题斜率一定为正,这个题斜率可以为负。
对于每一个询问,需要找到该询问处的最大值和最小值,因为位移可为负数,取绝对值后也可以很大。正因如此,我们需要两棵线段树,一棵存最大值,一棵存最小值。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <vector> 
#include <algorithm>
typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc(); 
    while (c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while (c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXQ = 600005, MAXN = 100005;

inline bool isop(char c) {
    return c == 'c' || c == 'q';
}

inline char readop() {
    char c = fgc();
    while (!isop(c)) c = fgc();
    return c;
}

// global variables

struct Line {
    LL k, b;
    Line() {}
    Line(LL k, LL b): k(k), b(b) {} 
    inline LL cal(LL x) {
        return k * x + b; 
    }
};

Line lstl[MAXN];
LL n, m, N, lstt[MAXN];

struct Query {
    LL time, x, k;
    char op;
} ques[MAXQ];

inline bool cmp(Line l1, Line l2, LL x) { // if l1 bigger than l2 on pos x
    return l1.cal(x) > l2.cal(x);
} 

inline double interx(Line l1, Line l2) {
    return double(l2.b - l1.b) / (l1.k - l2.k);
}

std::vector<LL> tmp; 

// seg tree

#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)

Line tmx[MAXQ << 2], tmn[MAXQ << 2];
bool imx[MAXQ << 2], imn[MAXQ << 2];

inline void addmx(int o, int l, int r, int ll, int rr, Line line) {
    if(l >= ll && r <= rr) {
        if(!imx[o]) {
            tmx[o] = line;
            imx[o] = true;
            return;
        }
        LL olv = tmx[o].cal(tmp[l]), orv = tmx[o].cal(tmp[r]), nlv = line.cal(tmp[l]), nrv = line.cal(tmp[r]);
        if(olv >= nlv && orv >= nrv) {
            return;
        }
        if(olv <= nlv && orv <= nrv) {
            tmx[o] = line;
            return;
        }
        double ix = interx(tmx[o], line);
        if(olv >= nlv) {
            if(ix <= tmp[mid]) {
                addmx(lch, l, mid, ll, rr, tmx[o]);
                tmx[o] = line;
            } else {
                addmx(rch, mid + 1, r, ll, rr, line);
            }
        } else {
            if(ix > tmp[mid]) {
                addmx(rch, mid + 1, r, ll, rr, tmx[o]);
                tmx[o] = line;
            } else {
                addmx(lch, l, mid, ll, rr, line);
            }
        }
        return;
    }
    if(ll <= mid) addmx(lch, l, mid, ll, rr, line);
    if(rr > mid) addmx(rch, mid + 1, r, ll, rr, line);
}

inline void addmn(int o, int l, int r, int ll, int rr, Line line) {
    if(l >= ll && r <= rr) {
        if(!imn[o]) {
            tmn[o] = line;
            imn[o] = true;
            return;
        }
        LL olv = tmn[o].cal(tmp[l]), orv = tmn[o].cal(tmp[r]), nlv = line.cal(tmp[l]), nrv = line.cal(tmp[r]);
        if(olv <= nlv && orv <= nrv) {
            return;
        }
        if(olv >= nlv && orv >= nrv) {
            tmn[o] = line;
            return;
        }
        double ix = interx(tmn[o], line);
        if(olv < nlv) {
            if(ix <= tmp[mid]) {
                addmn(lch, l, mid, ll, rr, tmn[o]);
                tmn[o] = line;
            } else {
                addmn(rch, mid + 1, r, ll, rr, line);
            }
        } else {
            if(ix > tmp[mid]) {
                addmn(rch, mid + 1, r, ll, rr, tmn[o]);
                tmn[o] = line;
            } else {
                addmn(lch, l, mid, ll, rr, line);
            }
        }
        return;
    }
    if(ll <= mid) addmn(lch, l, mid, ll, rr, line);
    if(rr > mid) addmn(rch, mid + 1, r, ll, rr, line);
}

inline LL quemx(int o, int l, int r, int x) {
    LL res = -1e15;
    if(imx[o]) res = std::max(res, tmx[o].cal(tmp[x]));
    if(l == r) return res;
    if(x <= mid) res = std::max(res, quemx(lch, l, mid, x));
    if(x > mid) res = std::max(res, quemx(rch, mid + 1, r, x));
    return res;
}

inline LL quemn(int o, int l, int r, int x) {
    LL res = 1e15;
    if(imn[o]) res = std::min(res, tmn[o].cal(tmp[x]));
    if(l == r) return res;
    if(x <= mid) res = std::min(res, quemn(lch, l, mid, x));
    if(x > mid) res = std::min(res, quemn(rch, mid + 1, r, x));
    return res;
}

// main

int main() {
    n = readint();
    m = readint();
    for(int i = 1; i <= n; i++) {
        lstl[i].b = readint();
    }
    for(int i = 1; i <= m; i++) {
        ques[i].time = readint();
        ques[i].op = readop();
        if(ques[i].op == 'c') {
            ques[i].x = readint();
            ques[i].k = readint();
        }
        tmp.push_back(ques[i].time);
    }
    tmp.push_back(-1);
    tmp.push_back(0);
    std::sort(tmp.begin(), tmp.end());
    tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
    N = tmp.size() - 1;
    for(int i = 1; i <= m; i++) {
        if(ques[i].op == 'c') {
            LL x = ques[i].x, 
                lst = std::lower_bound(tmp.begin(), tmp.end(), lstt[x]) - tmp.begin(), 
                now = std::lower_bound(tmp.begin(), tmp.end(), ques[i].time) - tmp.begin();
            addmx(1, 1, N, lst, now, lstl[x]);
            addmn(1, 1, N, lst, now, lstl[x]);
            lstl[x] = Line(ques[i].k, lstl[x].b + ques[i].time * (lstl[x].k - ques[i].k));
            lstt[x] = ques[i].time; 
        }
    }
    for(int i = 1; i <= n; i++) {
        LL lst = std::lower_bound(tmp.begin(), tmp.end(), lstt[i]) - tmp.begin();
        addmx(1, 1, N, lst, N, lstl[i]);
        addmn(1, 1, N, lst, N, lstl[i]);
    }
    for(int i = 1; i <= m; i++) {
        if(ques[i].op == 'q') {
            LL now = std::lower_bound(tmp.begin(), tmp.end(), ques[i].time) - tmp.begin(),
                ans1 = quemx(1, 1, N, now), ans2 = -quemn(1, 1, N, now);
            printf("%lld\n", std::max(ans1, ans2));
        }
    }
    return 0;
}