题意 路上有 n 个加油站 每个加油站的价格可能不同 你的油箱容积为 v 问从起点开车到终点加油至少用多少钱

贪心 每次都让油箱里面便宜的油最多就行了 在每个站点 i 有两种情况

1. i 点把油加满跑完都没有更便宜的 那么在 i 点肯定要加满 然后开到 i+1 点去

2. i 点把油加满能跑到第一个比 i 点更便宜的 j 点或者到了终点 j 那么只用把油加到能到 j 点 然后直接开到 j 点

然后把每个点加油用的钱加起来就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <cstdio>
using namespace std;
const int N = 100005;
typedef long long ll;
ll len[N], cost[N], pri[N], v;

int main()
{
    int T, n;
    scanf("%d", &T);

    while(T--)
    {
        scanf("%d%lld", &n, &v);
        int flag = 0;

        for(int i = 0; i < n; i++)
        {
            scanf("%lld%lld%lld", &len[i], &cost[i], &pri[i]);
            if(len[i] * cost[i] > v) flag = 1;
        }

        if(flag)
        {
            puts("Impossible");
            continue;
        }

        int i = 0, j;
        ll r = 0, ans = 0, t;                 //r记录到i点还剩多少油
        while(i < n)
        {
            j = i + 1, t = len[i] * cost[i];  //t记录到下一个便宜的点用了多少油

            //往前走直到找到一个更便宜的站j  或者油箱跑完
            while( j < n && pri[j] >= pri[i] && v - t >= cost[j] * len[j])
            {
                t += len[j] * cost[j];
                ++j;
            }


            if( j >= n || pri[j] < pri[i])  //j点油第一个比i点便宜  加到能到j
            {
                if(r > t)  r -= t;
                else
                {
                    ans += (t - r)  * pri[i];
                    r = 0;
                }
                i = j;
            }

            else  //油跑完都没更便宜的 加满 到下一站
            {
                ans +=  (v - r) * pri[i];
                r = v - len[i] * cost[i];
                i++;
            }
        }

        printf("%lld\n", ans);
    }

    return 0;
}

Dakar Rally Time Limit:2 Seconds Memory Limit:65536 KB

Description

The Dakar Rally is an annual Dakar Series rally raid type of off-road race, organized by the Amaury Sport Organization. The off-road endurance race consists of a series of routes. In different routes, the competitors cross dunes, mud, camel grass, rocks, erg and so on.

Because of the various circumstances, the mileages consume of the car and the prices of gas vary from each other. Please help the competitors to minimize their payment on gas.

Assume that the car begins with an empty tank and each gas station has infinite gas. The racers need to finish all the routes in order as the test case descripts.

Input

There are multiple test cases. The first line of input contains an integer T (T ≤ 50) indicating the number of test cases. Then T test cases follow.

The first line of each case contains two integers: n – amount of routes in the race; capacity – the capacity of the tank.

The following n lines contain three integers each: mileagei – the mileage of the ith route; consumei – the mileage consume of the car in the ith route , which means the number of gas unit the car consumes in 1 mile; pricei – the price of unit gas in the gas station which locates at the beginning of the ith route.

All integers are positive and no more than 105.

Output

For each test case, print the minimal cost to finish all of the n routes. If it’s impossible, print “Impossible” (without the quotes).

Sample Input

2 2 30 5 6 9 4 7 10 2 30 5 6 9 4 8 10

Sample Output

550 Impossible

题意 长度为n的数组上有个长度为k的滑窗从左向右移动 求每次移动后滑窗区间的最小值和最大值 输出两行 第一行所有最小值 第二行所有最大值

可以用线段树来做 但是单调队列更简单

单调递增队列： 队尾单调入队(入队元素大于队尾元素时直接入队 否则队尾出队直到队尾元素小于入队元素或者队列为空) 队首队尾都可以出队

求最小值时 先判断队首元素是否在滑窗之内 不在队首就出队 然后队首元素就是滑窗中的最小值了 求最大值用单减队列就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <cstdio>
using namespace std;
const int N = 1e6 + 5;
int a[N], q[N], t[N];
int front, rear, n, k;

#define NOTMONO (!op && a[i] < q[rear - 1]) || (op && a[i] > q[rear - 1])
void getMonoQueue(int op) //op = 0 时单增队列  op = 1 时单减队列
{
    front = rear = 0;
    for(int i = 0; i < n; ++i)
    {
        while( rear > front && (NOTMONO)) --rear;
        t[rear] = i;      //记录滑窗滑到i点的时间
        q[rear++] = a[i];
        while(t[front] <= i - k) ++front;  //保证队首元素在滑窗之内
        if(i > k - 2)
            printf("%d%c", q[front], i == n - 1 ? '\n' : ' ');
    }
}

int main()
{
    while (~scanf("%d%d", &n, &k))
    {
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        getMonoQueue(0); //单增队列维护最小值
        getMonoQueue(1); //单减队列维护最大值
    }

    return 0;
}

//Last modified :   2015-07-06 12:16

Sliding Window

Description
An array of size n ≤ 10 6 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3. Window position Minimum value Maximum value [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3 -1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7

Your task is to determine the maximum and minimum values in the sliding window at each position.

Input

The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.

Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

Sample Input

8 3 1 3 -1 -3 5 3 6 7

Sample Output

-1 -3 -3 -3 3 3 3 3 5 5 6 7

题意 输出八数码问题从给定状态到12345678x的路径

用康托展开将排列对应为整数 即这个排列在所有排列中的字典序 然后就是基础的BFS了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5, M = 9;
int x[4] = { -1, 1, 0, 0};
int y[4] = {0, 0, -1, 1};
int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
int puz[N][M], nex[N], dir[N], vis[N], q[N];

int getCantor(int a[])  //康托展开  将排列转化为整数
{
    int ret = 0;
    for(int i = 0; i < M; ++i)
    {
        for(int j = i + 1; j < M; ++j)
            if(a[j] < a[i]) ret += fac[M - i - 1];
    }
    return ret;
}

void bfs()
{
    int t[M] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
    int id = getCantor(t);
    dir[id] = -1;

    memcpy(puz[id], t, sizeof(t));
    memset(vis, 0, sizeof(vis));

    int r, c, k, nr, nc, nk, nid;
    int front = 0, rear = 0;
    q[rear++] = id;
    vis[id] = 1;

    while(front < rear)
    {
        int id = q[front++];
        memcpy(t, puz[id], sizeof(t));
        for(k = 0; t[k]; ++k);  //找0的位置
        r = k / 3, c = k % 3;  //一维转二维

        for(int i = 0; i < 4; ++i)
        {
            nr = r + x[i], nc = c + y[i], nk = nr * 3 + nc;

            if(nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
            swap(t[k], t[nk]);
            nid = getCantor(t);
            memcpy(puz[nid], t, sizeof(t));
            swap(t[k], t[nk]);

            if(vis[nid]) continue;
            vis[nid] = 1;
            q[rear++] = nid;
            nex[nid] = id;
            dir[nid] = i;
        }
    }
}

int main()
{
    char t[5], sdir[] = "durl";
    int s[M], id;
    bfs();

    while(~scanf("%s", t))
    {
        s[0] = t[0] == 'x' ? 0 : t[0] - '0';
        for(int i = 1; i < M; ++i)
        {
            scanf("%s", t);
            s[i] = t[0] == 'x' ? 0 : t[0] - '0';
        }

        id = getCantor(s);
        if(!vis[id]) puts("unsolvable");
        else
        {
            while(dir[id] >= 0)
            {
                printf("%c", sdir[dir[id]]);
                id = nex[id];
            }
            puts("");
        }
    }
    return 0;
}
//Last modified :   2015-07-05 11:15

Eight

Problem Description

The 15-puzzle has been around for over 100 years; even if you don’t know it by that name, you’ve seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let’s call the missing tile ‘x’; the object of the puzzle is to arrange the tiles so that they are ordered as: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x
where the only legal operation is to exchange ‘x’ with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12 13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x r-> d-> r->
The letters in the previous row indicate which neighbor of the ‘x’ tile is swapped with the ‘x’ tile at each step; legal values are ‘r’,’l’,’u’ and ‘d’, for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing ‘x’ tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.
Input

You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus ‘x’. For example, this puzzle
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output

You will print to standard output either the word ``unsolvable’’, if the puzzle has no solution, or a string consisting entirely of the letters ‘r’, ‘l’, ‘u’ and ‘d’ that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.
Sample Input

2 3 4 1 5 x 7 6 8
Sample Output

ullddrurdllurdruldr

题意 对一个数组有四种操作

对每个操作4输出对应最小值和最大值

基础的线段树 在湘潭卡了好久没写出来
线段树维护三个值 区间最大值 maxv, 区间最小值minv, 区间增加的值add
操作1是很容易实现的 操作2和3比1要复杂些 初一想要对每个值单独进行操作 这样肯定会T的 毕竟那样用线段树就没意义了 后来发现每次更新时对应区间包含的所有最大区间节点的maxv 和 minv是可以确定的

然后知道了父区间的maxv,minv后 通过pashdown函数就可以在需要时再对子区间进行更新 因为子区间的所有值都是在父区间的minv和maxv之间 然后就看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

#include <bits/stdc++.h>
#define lc p<<1, s, mid
#define rc p<<1|1, mid+1, e
#define mid ((s+e)>>1)
using namespace std;
const int N = 200005;
int maxv[N * 4], minv[N * 4], add[N * 4];

void pushup(int p)
{
    maxv[p] = max(maxv[p << 1], maxv[p << 1 | 1]);
    minv[p] = min(minv[p << 1], minv[p << 1 | 1]);
}

void pushdown(int p)
{
    int l = p << 1;
    int r = p << 1 | 1;

    if(add[p])
    {
        add[l] += add[p];
        add[r] += add[p];
        minv[l] += add[p];
        minv[r] += add[p];
        maxv[l] += add[p];
        maxv[r] += add[p];
        add[p] = 0;
    }

    //子区间的所有值肯定都父区间的minv~maxv之间
    minv[l] = max(minv[l], minv[p]);
    minv[l] = min(minv[l], maxv[p]);
    maxv[l] = max(maxv[l], minv[p]);
    maxv[l] = min(maxv[l], maxv[p]);

    minv[r] = max(minv[r], minv[p]);
    minv[r] = min(minv[r], maxv[p]);
    maxv[r] = max(maxv[r], minv[p]);
    maxv[r] = min(maxv[r], maxv[p]);
}

void build(int p, int s, int e)
{
    if(s == e)
    {
        scanf("%d", &maxv[p]);
        minv[p] = maxv[p];
        return;
    }
    build(lc);
    build(rc);
    pushup(p);
}

void update(int p, int s, int e, int l, int r, int v, int op)
{
    if(s >= l && e <= r)
    {
        if(op == 1) //将[l,r]区间的所有值都加上v
        {
            add[p] += v;
            minv[p] += v;
            maxv[p] += v;
        }
        else if (op == 2)  //将[l,r]区间中所有大于v的值都改为v
        {
            maxv[p] = min(maxv[p], v);
            minv[p] = min(minv[p], v);
        }
        else  //op = 3  将[l,r]区间中的所有小于v的值都改为v
        {
            maxv[p] = max(v, maxv[p]);
            minv[p] = max(v, minv[p]);
        }
        return;
    }
    pushdown(p);
    if(l <= mid) update(lc, l, r, v, op);
    if(r > mid) update(rc, l, r, v, op);
    pushup(p);
}

int query(int p, int s, int e, int l, int r, int op)
{
    if(s == l && e == r)//op = 0 时查询最小值  op = 1 时查询最大值
        return op ? maxv[p] : minv[p];
    pushdown(p);
    if(r <= mid) return query(lc, l, r, op);
    if(l > mid) return query(rc, l, r, op);
    if(op) return max(query(lc, l, mid, op), query(rc, mid + 1, r, op));
    return min(query(lc, l, mid, op), query(rc, mid + 1, r, op));
}

int main()
{
    int T, n, q, l, r, op, c, ax, in;
    scanf("%d", &T);
    while(T--)
    {
        memset(add, 0, sizeof(add));
        scanf("%d%d", &n, &q);
        build(1, 1, n);
        while(q--)
        {
            scanf("%d%d%d", &op, &l, &r);
            if(op == 4)
            {
                ax = query(1, 1, n, l, r, 1);
                in = query(1, 1, n, l, r, 0);
                printf("%d %d\n", in, ax);
            }
            else
            {
                scanf("%d", &c);
                update(1, 1, n, l, r, c, op);
            }
        }
    }
    return 0;
}

Segment Tree

Problem Description:

A contest is not integrity without problems about data structure.
There is an array a[1],a[2],…,a[n]. And q questions of the following 4 types: • 1 l r c - Update a[k] with a[k]+c for all l≤k≤r
• 2 l r c - Update a[k] with min{a[k],c} for all l≤k≤r;
• 3 l r c - Update a[k] with max{a[k],c} for all l≤k≤r;
• 4 l r - Ask for min{a[k]:l≤k≤r} and max{a[k]:l≤k≤r}.

Input

The first line contains a integer T(no more than 5) which represents the number of test cases.

For each test case, the first line contains 2 integers n,q (1≤n,q≤200000).

The second line contains n integers a1,a2,…,an which indicates the initial values of the array (|ai|≤).

Each of the following q lines contains an integer t which denotes the type of i-th question. If t=1,2,3, 3 integers l,r,c follows. If t=4, 2 integers l,r follows. (1≤ti≤4,1≤li≤ri≤n)

If t=1, |ci|≤2000;

If t=2,3, |ci|≤10^9.

Output

For each question of type 4, output two integers denote the minimum and the maximum.

Sample Input

1
1 1
1
4 1 1

Sample Output

1 1

Source
XTU OnlineJudge

题意 中文

简单的Topo排序 用vector实现邻接表比较方便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

vector<int> e[N];
vector<int>::iterator it;
int n, m, ideg[N];

bool topo()
{
    int cur;
    queue<int> q;
    for(int i = 1; i <= n; ++i)
        if(!ideg[i]) q.push(i);

    while(!q.empty())
    {
        cur = q.front();
        q.pop();
        for(it = e[cur].begin(); it != e[cur].end(); ++it)
        {
            if(!ideg[*it]) continue;
            --ideg[*it];
            if(!ideg[*it]) q.push(*it);
        }
    }

    for(int i = 1; i <= n; ++i)
        if(ideg[i]) return false;
    return true;
}

int main()
{
    int cas, a, b;
    scanf("%d", &cas);
    while(cas--)
    {
        memset(ideg, 0, sizeof(ideg));
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i) e[i].clear();
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &a, &b);
            e[a].push_back(b);
            ++ideg[b];
        }
        puts(topo() ? "Correct" : "Wrong");
    }
    return 0;
}
//Last modified :   2015-05-25 09:05

时间限制: 10000ms

单点时限: 1000ms
内存限制: 256MB

描述

由于今天上课的老师讲的特别无聊，小Hi和小Ho偷偷地聊了起来。

小Ho：小Hi，你这学期有选什么课么？

小Hi：挺多的，比如XXX1,XXX2还有XXX3。本来想选YYY2的，但是好像没有先选过YYY1，不能选YYY2。

小Ho：先修课程真是个麻烦的东西呢。

小Hi：没错呢。好多课程都有先修课程，每次选课之前都得先查查有没有先修。教务公布的先修课程记录都是好多年前的，不但有重复的信息，好像很多都不正确了。

小Ho：课程太多了，教务也没法整理吧。他们也没法一个一个确认有没有写错。

小Hi：这不正是轮到小Ho你出马的时候了么！

小Ho：哎？？

我们都知道大学的课程是可以自己选择的，每一个学期可以自由选择打算学习的课程。唯一限制我们选课是一些课程之间的顺序关系：有的难度很大的课程可能会有一些前置课程的要求。比如课程A是课程B的前置课程，则要求先学习完A课程，才可以选择B课程。大学的教务收集了所有课程的顺序关系，但由于系统故障，可能有一些信息出现了错误。现在小Ho把信息都告诉你，请你帮小Ho判断一下这些信息是否有误。错误的信息主要是指出现了”课程A是课程B的前置课程，同时课程B也是课程A的前置课程”这样的情况。当然”课程A是课程B的前置课程，课程B是课程C的前置课程，课程C是课程A的前置课程”这类也是错误的。

提示：拓扑排序

输入

第1行：1个整数T，表示数据的组数T(1 <= T <= 5)
接下来T组数据按照以下格式：
第1行：2个整数，N,M。N表示课程总数量，课程编号为1..N。M表示顺序关系的数量。1 <= N <= 100,000. 1 <= M <= 500,000
第2..M+1行：每行2个整数，A,B。表示课程A是课程B的前置课程。

输出

第1..T行：每行1个字符串，若该组信息无误，输出”Correct”，若该组信息有误，输出”Wrong”。
样例输入 2 2 2 1 2 2 1 3 2 1 2 1 3 样例输出 Wrong Correct

题意 公司中有n个员工 除了boss 每个员工都有自己的上司 自己下属的下属也是自己的下属 当给一个员工分配任务时 这个员工会把任务也分配到自己的所有下属 每个员工都只做最后一个被分配的任务 对于每个C x 输出员工x正在做的任务 没有就输出-1

把员工的关系数建成类似并查集的结构 把每个直接分配任务的员工的任务和任务分配时间保存起来 查询时只要找这个员工所有父节点中最晚分配的任务

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
struct employee{
    int task, t;
} e[N];
int par[N];

int main()
{
    int cas, a, b, n, m;
    char op[5];
    scanf("%d", &cas);
    for(int k = 1; k <= cas; ++k)
    {
        printf("Case #%d:\n", k);
        memset(par, -1, sizeof(par));
        scanf("%d", &n);
        for(int i = 1; i < n; ++i)
        {
            e[i].t = e[i].task = 0;
            scanf("%d%d", &a, &b), par[a] = b;
        }
        e[n].t = e[n].task = 0;

        scanf("%d", &m);
        int t = 0, last, ans;
        while(m--)
        {
            scanf("%s%d", op, &a);
            if(op[0] == 'C')
            {
                last = 0;//所有祖先节点最晚任务的时间
                while(a != -1)
                {
                    if(e[a].t > last)
                        last = e[a].t, ans = e[a].task;
                    a = par[a];
                }
                printf("%d\n", last ? ans : -1);
            }
            else
            {
                scanf("%d", &b);
                e[a].task = b, e[a].t = ++t;
            }
        }
    }
    return 0;
}
//Last modified :   2015-04-22 20:48

Assign the task

Problem Description

There is a company that has N employees(numbered from 1 to N),every employee in the company has a immediate boss (except for the leader of whole company).If you are the immediate boss of someone,that person is your subordinate, and all his subordinates are your subordinates as well. If you are nobody’s boss, then you have no subordinates,the employee who has no immediate boss is the leader of whole company.So it means the N employees form a tree.
The company usually assigns some tasks to some employees to finish.When a task is assigned to someone,He/She will assigned it to all his/her subordinates.In other words,the person and all his/her subordinates received a task in the same time. Furthermore,whenever a employee received a task,he/she will stop the current task(if he/she has) and start the new one.
Write a program that will help in figuring out some employee’s current task after the company assign some tasks to some employee.
Input

The first line contains a single positive integer T( T <= 10 ), indicates the number of test cases.
For each test case:
The first line contains an integer N (N ≤ 50,000) , which is the number of the employees.
The following N - 1 lines each contain two integers u and v, which means the employee v is the immediate boss of employee u(1<=u,v<=N).
The next line contains an integer M (M ≤ 50,000).
The following M lines each contain a message which is either
“C x” which means an inquiry for the current task of employee x
or
“T x y”which means the company assign task y to employee x.
(1<=x<=N,0<=y<=10^9)
Output

For each test case, print the test case number (beginning with 1) in the first line and then for every inquiry, output the correspond answer per line.
Sample Input

1 5 4 3 3 2 1 3 5 2 5 C 3 T 2 1 C 3 T 3 2 C 3
Sample Output

Case /#1: -1 1 2
Source

2011 Multi-University Training Contest 14 - Host by FZU

题意 有n个连在一起的地道 接下来有m个操作 D x 炸掉x号地道 炸掉后x所在的区间就不连续了 Q x 查询输出包括x的最大连续区间长度 R修复最后一个被炸的地道 注意输入R时可能并没有需要修复的地道

线段树的区间合并问题 线段树要维护3个信息

len 对应区间的最大连续长度

ll 对应区间最左端的一段连续长度

lr 对应区间最右端的一段连续长度

那么双亲节点的这些信息和孩子节点有什么关系呢容易发现

双亲的len 是 左孩子的len 右孩子的len 左孩子的右端长度+右孩子的左端长度 这三个的最大值

双亲的ll 如果左孩子整个区间都是连续的话 ll就等于左孩子的len加上右孩子的左端长度了

双亲的lr 如果右孩子整个区间都是连续的话 lr就等于右孩子的len加上左孩子的右端长度了

于是就知道pushup函数怎么写了 请看代码

知道这些信息又怎么查询包括x点的最大区间长度呢

肯定是在包含x的区间里面查的

如果根区间整个区间都是连续的 那么根区间长度就是答案了

如果x在左孩子的右端连续段或者右孩子的左端连续段里 那么这两段的和就是答案了

否则就继续查询x所属的孩子区间咯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include <bits/stdc++.h>
#define lc lp, s, mid
#define rc rp, mid+1, e
#define lp p<<1
#define rp p<<1|1
#define mid ((s+e)>>1)
using namespace std;
const int N = 50005;
int len[N * 4], lr[N * 4], ll[N * 4];
int n, m;

void pushup(int p, int s, int e)
{
    len[p] = max(len[lp], len[rp]);
    len[p] = max(len[p], lr[lp] + ll[rp]);
    ll[p] = ll[lp], lr[p] = lr[rp];
    if(ll[p] == mid - s + 1) ll[p] += ll[rp];
    if(lr[p] == e - mid) lr[p] += lr[lp];
}

void build(int p, int s, int e)
{
    if(s == e)
    {
        len[p] = ll[p] = lr[p] = 1;
        return;
    }
    build(lc);
    build(rc);
    pushup(p, s, e);
}

void update(int p, int s, int e, int x, int v)
{
    if(s == e && e == x)
    {
        len[p] = ll[p] = lr[p] = v;
        return;
    }
    if(x <= mid) update(lc, x, v);
    else update(rc, x, v);
    pushup(p, s, e);
}

int query(int p, int s, int e, int x)
{
    if(len[p] == 0 || len[p] == e - s + 1)	return len[p];
    if(x <= mid)
        return x > mid - lr[lp] ? lr[lp] + ll[rp] : query(lc, x);
    return x <= ll[rp] + mid ? ll[rp] + lr[lp] : query(rc, x);
}

int main()
{
    char op[10];
    int p;
    while(~scanf("%d%d", &n, &m))
    {
        stack<int> s;
        build(1, 1, n);
        while(m--)
        {
            scanf("%s", op);
            if(op[0] == 'R' && !s.empty())
            {
                p = s.top(), s.pop();
                update(1, 1, n, p, 1);
            }
            else if(op[0] == 'D')
            {
                scanf("%d", &p);
                update(1, 1, n, p, 0);
                s.push(p);
            }
            else
            {
                scanf("%d", &p);
                printf("%d\n", query(1, 1, n, p));
            }
        }
    }
    return 0;
}

题意 输入n个数 然后有两种操作 输入0时将给定区间所有数都变为自己的开方 输入1输出给定区间所有数的和

虽然是区间更新 但每个点更新的不一样 因此只能对单点进行更新 其实一个点最多被更新7次 2^64开平方7次后就变为1了 如果某个区间的数都变为了1 那么对这个区间的开方就不用考虑了 另外要注意给你的区间可能是反的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <bits/stdc++.h>
#define lc p<<1,s,mid
#define rc p<<1|1,mid+1,e
#define mid ((s+e)>>1)
using namespace std;
typedef long long LL;
const int N = 100005;
LL sum[N * 4];

void pushup(int p)
{
    sum[p] = sum[p << 1] + sum[p << 1 | 1];
}

void build(int p, int s, int e)
{
    if(s == e)
    {
        scanf("%lld", &sum[p]);
        return;
    }
    build(lc);
    build(rc);
    pushup(p);
}

void update(int p, int s, int e, int l, int r)
{
    if(sum[p] == e - s + 1) return;  //[e,s]区间所有数都为1
    if(s == e)
    {
        sum[p] = sqrt(sum[p]);
        return;
    }
    if(l <= mid) update(lc, l, r);
    if(r > mid) update(rc, l, r);
    pushup(p);
}

LL query(int p, int s, int e, int l, int r)
{
    if(s == l && e == r) return sum[p];
    if(r <= mid) return query(lc, l, r);
    if(l > mid) return query(rc, l, r);
    return query(lc, l, mid) + query(rc, mid + 1, r);
}

int main()
{
    int n, m, a, b, c, k = 0;
    while(~scanf("%d", &n))
    {
        printf("Case #%d:\n", ++k);
        build(1, 1, n);
        scanf("%d", &m);
        while(m--)
        {
            scanf("%d%d%d", &c, &a, &b);
            if(b < a) swap(a, b);
            if(c) printf("%lld\n", query(1, 1, n, a, b));
            else update(1, 1, n, a, b);
        }
        puts("");
    }
    return 0;
}

Can you answer these queries?

Problem Description

A lot of battleships of evil are arranged in a line before the battle. Our commander decides to use our secret weapon to eliminate the battleships. Each of the battleships can be marked a value of endurance. For every attack of our secret weapon, it could decrease the endurance of a consecutive part of battleships by make their endurance to the square root of it original value of endurance. During the series of attack of our secret weapon, the commander wants to evaluate the effect of the weapon, so he asks you for help.
You are asked to answer the queries that the sum of the endurance of a consecutive part of the battleship line.
Notice that the square root operation should be rounded down to integer.
Input

The input contains several test cases, terminated by EOF.
For each test case, the first line contains a single integer N, denoting there are N battleships of evil in a line. (1 <= N <= 100000)
The second line contains N integers Ei, indicating the endurance value of each battleship from the beginning of the line to the end. You can assume that the sum of all endurance value is less than 2 63.
The next line contains an integer M, denoting the number of actions and queries. (1 <= M <= 100000)
For the following M lines, each line contains three integers T, X and Y. The T=0 denoting the action of the secret weapon, which will decrease the endurance value of the battleships between the X-th and Y-th battleship, inclusive. The T=1 denoting the query of the commander which ask for the sum of the endurance value of the battleship between X-th and Y-th, inclusive.
Output

For each test case, print the case number at the first line. Then print one line for each query. And remember follow a blank line after each test case.
Sample Input

10 1 2 3 4 5 6 7 8 9 10 5 0 1 10 1 1 10 1 1 5 0 5 8 1 4 8
Sample Output

Case /#1: 19 7 6
Source

The 36th ACM/ICPC Asia Regional Shanghai Site —— Online Contest

题意 在墙上贴n张海报 输入每张海报的的左右端点坐标 问最后可以看到多少张海报 能看到一点也是能看到

先把线段树初始化为0 输入一张海报 就把那个区间变成这张海报的序号 最后判断墙上有多少个不同的序号就行了

但是海报坐标的端点值高达10000000 直接用线段树会超时 但是注意到海报最多只有10000张 也就是最多有20000个不同的坐标 于是可以利用离散化的知识 把所有坐标排序 注意所有右端点坐标+1也要加入排序(注意1,10 ; 1,3; 7,10这种情况 如果右端点+1没加入排序的话可能使原来不相邻的变为相邻 这样就覆盖了本来没有覆盖的区间) 可以发现 把每个端点的坐标变为该点排序后的序号不会改变整个图形的结构 于是就可以用序号代替坐标了 大大减小了复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lc p<<1,s,mid
#define rc p<<1|1,mid+1,e
#define mid ((s+e)>>1)
#define CLR(A) memset(A,0,sizeof(A))
using namespace std;

const int N = 20005;
int col[N * 4], vis[N];
int le[N], ri[N], c[N * 2], ans;

void pushdown(int p)
{
    if(col[p] == -1) return;
    col[p << 1] = col[p << 1 | 1]  = col[p];
    col[p] = -1;
}

void update(int p, int s, int e, int l, int r, int v)
{
    if(s >= l && e <= r)
    {
        col[p] = v;
        return;
    }
    pushdown(p);
    if(l <= mid) update(lc, l, r, v);
    if(r > mid) update(rc, l, r, v);
}

void query(int p, int s, int e)
{
    if(col[p] != -1)
    {
        if(!vis[col[p]])
            vis[col[p]] = 1, ++ans;
        return;
    }
    query(lc);
    query(rc);
}

int compress(int n) //离散化
{
    int k = 0;
    for(int i = 0; i < n; ++i)
    {
        c[k++] = le[i];
        c[k++] = ri[i];
        c[k++] = ri[i] + 1;
    }
    sort(c, c + k);
    return unique(c, c + k) - c - 1;
}

int main()
{
    int cas, m, n, l, r;
    scanf("%d", &cas);
    while(cas--)
    {
        scanf("%d", &m);
        for(int i = 0; i < m; ++i)
            scanf("%d%d", &le[i], &ri[i]);
        n = compress(m);

        ans = 0;
        CLR(col), CLR(vis);
        for(int i = 0; i < m; ++i)
        {
            l = lower_bound(c, c + n, le[i]) - c + 1;
            r = lower_bound(c, c + n, ri[i]) - c + 1;
            update(1, 1, n, l, r, i + 1);
        }
        vis[0] = 1;
        query(1, 1, n);
        printf("%d\n", ans);
    }
    return 0;
}

Mayor’s posters

Description
The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:

They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are placed given the information about posters’ size, their place and order of placement on the electoral wall.

Input

The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers l i and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= l i <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered l i, l i+1 ,… , ri.

Output

For each input data set print the number of visible posters after all the posters are placed.
The picture below illustrates the case of the sample input.

Sample Input

1 5 1 4 2 6 8 10 3 4 7 10

Sample Output

4

Source

Alberta Collegiate Programming Contest 2003.10.18

题意 有一个等差数列 从A开始 公差为B然后n个询问 每个询问给定l,t,m然后要求如果每次可以最多选择m个数 使这m个数-1 那么在t次操作中可以使l为左端点的最长序列中使所有数为0 输出这个最长序列的右端序号

定理 序列h1,h2,…,hn 可以在t次时间内(每次至多让m个元素减少1) 全部减小为0 当且仅当

*max(h1, h2, …, hn) <= t && h1 + h2 + … + hn <= m/t

那么就可以二分右端点来解决了 下限为l 上限为hi不超过t的最大i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <bits/stdc++.h>
typedef long long LL;
LL a, b, n, l, t, m;


LL getv(LL p)
{
    return a + (p - 1) * b;
}


LL getsum(LL r)
{
    return (getv(r) + getv(l)) * (r - l + 1) / 2;
}


int main()
{
    scanf("%lld%lld%lld", &a, &b, &n);
    while(n--)
    {
        scanf("%lld%lld%lld", &l, &t, &m);
        if(getv(l) > t) puts("-1");
        else
        {
            LL le = l, ri = (t - a) / b + 1, mid;
            while(le <= ri)
            {
                mid = (ri + le) / 2;
                if(getsum(mid) <= t * m) le = mid + 1;
                else ri = mid - 1;
            }
            printf("%lld\n", le - 1);
        }
    }
    return 0;
}

C. Tavas and Karafs

Karafs is some kind of vegetable in shape of an 1 × h rectangle. Tavaspolis people love Karafs and they use Karafs in almost any kind of food. Tavas, himself, is crazy about Karafs.

Each Karafs has a positive integer height. Tavas has an infinite 1-based sequence of Karafses. The height of the i-th Karafs is s**i = A + (i - 1) × B.

For a given m, let’s define an m-bite operation as decreasing the height of at most m distinct not eaten Karafses by 1. Karafs is considered as eaten when its height becomes zero.

Now SaDDas asks you n queries. In each query he gives you numbers l, t and m and you should find the largest number r such that l ≤ rand sequence s**l, s**l + 1, …, s**r can be eaten by performing m-bite no more than t times or print -1 if there is no such number r.
Input

The first line of input contains three integers A, B and n (1 ≤ A, B ≤ 106, 1 ≤ n ≤ 105).

Next n lines contain information about queries. i-th line contains integers l, t, m (1 ≤ l, t, m ≤ 106) for i-th query.

Output

For each query, print its answer in a single line.
Sample test(s)

input 2 1 4 1 5 3 3 3 10 7 10 2 6 4 8

output 4 -1 8 -1
input 1 5 2 1 5 10 2 7 4

output 1 2