POJ 2991

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

题目大意

有$N$条首尾相连的线段笔直连接指向上方。第$i$条线段长度为$L_i$。

有$C$条指令,指令$C_i$给出两个整数$S_i$和$A_i$,效果是使线段$S_i$和$S_i+1$之间的角度顺时针旋转$A_i$度。最初所有角度都是180度。

按顺序执行这$C$条指令,在每条指令执行之后,输出线段末端(第$N$条线段)的坐标。

思路

这题可以用线段树来搞,线段树维护向量(从第1条线段起点指向第N条线段终点)和旋转角度,叶子节点表示每条线段的向量和当前角度,其他节点表示这段区间的向量。

设已知两个叶子节点lr,其父节点i,执行第$C_i$指令后,第$S_i$条线段顺时针旋转$A_i$度有:
$ \begin{aligned} (v_{ix}, v_{iy}) & = (v_{lx}, v_{ly}) + (v_{rx}, v_{ry}) \begin{pmatrix} cos\theta & sin\theta\\ -sin\theta & cos\theta \end{pmatrix} \\ & = (v_{lx}, v_{ly}) + (v_{rx}cos\theta - v_{ry}sin\theta, v_{rx}sin\theta+ v_{ry}cos\theta)\\ &=(v_{lx}+v_{rx}cos\theta-v_{ry}sin\theta, v_{ly}+v_{rx}sin\theta+v_{ry}cos\theta)\\ \therefore & \begin{cases} v_{ix} = v_{lx}+v_{rx}cos\theta-v_{ry}sin\theta\\ v_{iy} = v_{ly}+v_{rx}sin\theta+v_{ry}cos\theta \end{cases} \end{aligned}$

那么最后区间$[0, N)$的向量就是答案。

AC代码

/*************************************************************************
    > File Name: 2991.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-14 Thu 17:38:50 HKT
 ************************************************************************/

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

const int ST=1<<17;
const int MAXN = 10000 + 5;
const int MAXC = 10000 + 5;
const double PI = acos(-1);

int N, C;
int L[MAXN]; // 长度
int S[MAXC], A[MAXC]; // 操作线段,旋转角度

double vx[ST], vy[ST], angle[ST];
double prva[MAXN];

void init(int k, int l, int r) { // k节点编号,[l, r)
    angle[k] = vx[k] = 0;
    if(r - l == 1) vy[k] = L[l];
    else {
        int chl = (k<<1)+1, chr = (k<<1)+2, m = (l + r) >> 1;
        init(chl, l, m);
        init(chr, m, r);
        vy[k] = vy[chl] + vy[chr];
    }
}

void modify(int s, double a, int v, int l, int r) { // 后序[l, r)
    if(s <= l) return;
    else if(s < r) {
        int chl = (v<<1)+1, chr = (v<<1)+2, m = (l + r) >> 1;
        modify(s, a, chl, l, m);
        modify(s, a, chr, m, r);
        if(s<=m) angle[v] += a;

        double sins = sin(angle[v]), coss = cos(angle[v]); // 旋转
        vx[v] = vx[chl] + coss * vx[chr] - sins * vy[chr];
        vy[v] = vy[chl] + sins * vx[chr] + coss * vy[chr];
    }
}

void solve() {
    init(0, 0, N);
    // for(int i=0; i<N+1; ++i) printf("vy[%d]=%f\n", i, vy[i]);

    for(int i=1; i<N; ++i) prva[i] = PI;
    for(int i=0; i<C; ++i) {
        int s = S[i];
        double a = A[i] * PI / 180.0; // 化为弧度
        // printf("s=%d a=%f\n", s, a);
        modify(s, a-prva[s], 0, 0, N);
        prva[s] = a;
        printf("%.2f %.2f\n", vx[0], vy[0]); // [0,N)
    }

}

int main() {
#ifdef Oj
    freopen("2991.in", "r", stdin);
    // freopen("2991.out", "w", stdout);
#endif
    cin.sync_with_stdio(false);
    while(cin >> N >> C) {
        for(int i=0; i<N; ++i) cin >> L[i];
        for(int i=0; i<C; ++i) cin >> S[i] >> A[i];
        solve();
        printf("\n");
    }
    return 0;
}

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$的和。

思路

用线段树维护增量data和除增量以外其他值的和datb即可,第一次写超时了,没考虑用增量这个数组直接加。。

AC代码

/*************************************************************************
    > File Name: 3468_2.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-24 日 09:48:20 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100000+5;
int N, Q;
int A[MAXN];
ll data[MAXN << 2], datb [MAXN<<2]; // 增量data,除去data外的和datb

void add(int v, int l, int r, int L, int R, int a) { // 对区间[L,R)同时加上a
    if(R<=l || L>=r) return;
    else if(l>=L && r <= R) data[v] += a; // 包含,增量
    else { // 交集
        datb[v] += (min(R, r) - max(L, l))*a; // datb
        int chl = (v<<1)+1, chr=(v<<1)+2, m = (l+r)>>1;
        add(chl, l, m, L, R, a);
        add(chr, m, r, L, R, a);
    }

}

ll query(int v, int l, int r, int L, int R) { // 查询[L, R)上的和
    if(R<=l || L>=r) return 0;
    else if(l>=L && r<=R) return datb[v]+(r-l)*data[v]; // datb+增量
    else {
        ll res = (min(R, r) - max(L, l))*data[v]; // 增量
        int chl = (v<<1)+1, chr=(v<<1)+2, m = (l+r)>>1;
        res += query(chl, l, m, L, R);
        res += query(chr, m, r, L, R);
        return res;
    }
}

void solve() {
    char op;
    int a, b, c;
    for(int i=0; i<N; ++i) add(0, 0, N, i, i+1, A[i]);

    for(int i=0; i<Q; ++i) {
        getchar();
        scanf("%c%d%d", &op, &a, &b);
        if(op == 'Q') printf("%lld\n", query(0, 0, N, a-1, b));
        else {
            scanf("%d", &c);
            add(0, 0, N, a-1, b, c);
        }
    }

}

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

POJ 2104

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

题目大意

给定数列$a_1, a_2, \cdots, a_n$和$m$个三元组表示的查询。对于每个查询$(i, j, k)$,输出$a_i, a_{i+1}, \cdots, a_j$的升序排列中第$k$个数。

思路

线段树+二分搜索,每个节点保存一个递增数列,即归并树。

这题也有平方分割法。

AC代码

/*************************************************************************
    > File Name: 2104_2.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-31 日 10:42:03 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100000 + 23;
vector<int> tree[MAXN<<2]; // 线段树每个节点保存一个数列,归并树
int A[MAXN];
int N, M;

void build(int k, int l, int r) {
    if(r - l == 1)  // 叶子节点
        tree[k].push_back(A[l]);
    else {
        int chl = (k<<1) + 1, chr = (k<<1) + 2, m = (l+r) >> 1;
        build(chl, l, m);
        build(chr, m, r);
        tree[k].resize(r - l);
        merge(tree[chl].begin(), tree[chl].end(), tree[chr].begin(), tree[chr].end(), tree[k].begin()); // std::merge()大法好,归并函数
    }
}

int query(int k, int l, int r, int L, int R, int x) { // 查询[L, R)上<=x的个数
    if(R<=l || L>=r) return 0; // 无交集
    else if(L<=l && R>=r) // 完全包含
        return upper_bound(tree[k].begin(), tree[k].end(), x) - tree[k].begin(); // 二分搜索出<=x的数量
    else {
        int chl = (k<<1) + 1, chr = (k<<1) + 2, m = (l+r) >> 1;
        return query(chl, l, m, L, R, x) + query(chr, m, r, L, R, x);
    }
}

void solve() {
    build(0, 0, N);
    sort(A, A+N);
    for (int i = 0; i < M; ++i) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        // 二分
        int lb = -1, ub = N-1; // (lb, ub]
        while(ub - lb > 1) {
            int mid = (lb + ub) >> 1;
            if(query(0, 0, N, l-1, r, A[mid]) >= k) ub = mid;
            else lb = mid;
        }
        printf("%d\n", A[ub]);
    }
}

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

POJ 3368

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

题目大意

给定不减数列$a_1, a_2, \cdots, a_n$和$q$个查询。每次询问区间$[l, r]$上的出现最多的数的次数。

思路

记录每个数字第一次出现的位置就行了,然后原数组中的每个数字的个数就是下一个数字的位置减去当前数字的位置,用线段树来维这些数字的个数就行了。。。

AC代码

/*************************************************************************
    > File Name: 3368.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-31 日 16:34:55 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 100000+5;
int tree[MAXN*3];
vector<int> pos;
int N, Q;
void build(int v, int l, int r) { // [l, r)
    if(r - l == 1) {
        tree[v] = pos[r] - pos[l];
        // printf("tree[%d] num: %d\n", v, pos[r]-pos[l]);
    }
    else {
        int chl = (v<<1) + 1, chr = (v<<1) + 2, m = (l+r) >> 1;
        build(chl, l, m);
        build(chr, m, r);
        tree[v] = max(tree[chl], tree[chr]);
    }
}

int query(int v, int l, int r, int L, int R) { // [l, r)
    // printf("l:%d r:%d L:%d R:%d\n", l, r, L, R);
    if(L==R) return 1;
    else if(L >= r || R <= l) return 0;
    else if(L<=l && r <= R)
        return tree[v];
    else {
        int chl = (v<<1) + 1, chr = (v<<1) + 2, m = (l+r) >> 1;
        return max(query(chl, l, m, L, R), query(chr, m, r, L, R));
    }
}

void solve() {
    build(0, 0, pos.size() - 1);
    for (int i = 0; i < Q; ++i) {
        int l, r;
        scanf("%d%d", &l, &r); --l;
        int lp = lower_bound(pos.begin(), pos.end(), l) - pos.begin();
        int rp = lower_bound(pos.begin(), pos.end(), r) - pos.begin();
        // printf("pos[%d] = %d pos[%d]=%d\n", lp, pos[lp], rp, pos[rp]);
        if(pos[lp] == l && pos[rp] == r)
            printf("%d\n", query(0, 0, pos.size()-1, lp, rp));
        else if(pos[lp] == l && pos[rp] != r)
            printf("%d\n", max(query(0, 0, pos.size()-1, lp, rp-1), r-pos[rp-1]));
        else if(pos[lp] != l && pos[rp] == r)
            printf("%d\n", max(query(0, 0, pos.size()-1, lp, rp), pos[lp] - l));
        else {
            if(lp == rp) printf("%d\n", r - l);
            else printf("%d\n", max(r-pos[rp-1], max(query(0, 0, pos.size()-1, lp, rp-1), pos[lp] - l)));
        }
    }

}

int main() {
#ifdef Oj
    freopen("3368.in", "r", stdin);
    // freopen("3368.out", "w",stdout);
#endif
    while(scanf("%d%d", &N, &Q) == 2 && N) {
        int lst = -100020, cur;
        pos.clear();
        for(int i=0; i<N; ++i) {
            scanf("%d", &cur);
            if(cur != lst) {
                pos.push_back(i);
                lst = cur;
            }
        }
        pos.push_back(N);
        solve();
    }
    return 0;
}

HDOJ 1166

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1166

题目大意

C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。

中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:”你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:”我知错了。。。”但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.

思路

线段树来搞,经典线段树题目。

人数居然可以为负= =

AC代码

/*************************************************************************
    > File Name: 1166.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-18 一 15:11:49 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 50000+5;
int T, N;
int data[MAXN];
int tree[MAXN<<1];

void build(int v, int l, int r) { // [l, r),建树
    if(r - l == 1) {
        // printf("l: %d r: %d v:%d\n", l, r, v);
        tree[v] = data[l];
    }
    else {
        int chl = (v<<1)+1, chr = (v<<1)+2, m = (l + r) >> 1;
        build(chl, l, m);
        build(chr, m, r);
        tree[v] = tree[chl] + tree[chr];
    }
}

void update(int v, int l, int r, int k, int a) { // 第k个数据增加a,[l, r)
    if(k<l || k>=r) return;

    if(r-l == 1) { // 叶子节点
        tree[v] += a;
    }
    else {
        int chl = (v<<1)+1, chr = (v<<1)+2, m = (l + r) >> 1;
        if(k<m) update(chl, l, m, k, a); // k在左半部分
        else update(chr, m, r, k, a); // 否则就是右半部分
        tree[v] = tree[chl] + tree[chr];
    }
}

int query(int v, int l, int r, int s, int e) { // 求第[s, e)的和,[l, r)
    if(l>=e || r<=s) return 0;
    if(l >= s && r <= e) return tree[v];
    int chl = (v<<1)+1, chr = (v<<1)+2, m = (l + r) >> 1;
    // printf("l: %d m:%d r: %d v:%d s:%d e: %d\n", l, m, r, v, s, e);
    int ans = 0;
    if(m >= s) ans += query(chl, l, m, s, e); // m的前半部分到s是需要的
    if(m < e) ans += query(chr, m, r, s, e); // m的后半部分到e是需要的
    return ans;
}

void solve() {
    // memset(tree, 0, sizeof(tree));
    build(0, 0, N);
    // cout << query(0, 0, N, 1, 3) << endl;

    char cmd[10];
    int a, b;
    while(scanf("%s", cmd) && cmd[0] != 'E') {
        // cout << cmd << endl;
        scanf("%d%d", &a, &b);
        if(cmd[0] == 'A')
            update(0, 0, N, a-1, b);
        else if(cmd[0] == 'S')
            update(0, 0, N, a-1, -b);
        else if(cmd[0] == 'Q')
            printf("%d\n", query(0, 0, N, a-1, b));
    }
}

int main()
{
#ifdef Oj
    freopen("1166.in", "r", stdin);
#endif
    scanf("%d", &T);
    for(int t=0; t<T; ++t) {
        scanf("%d", &N);
        for(int i=0; i<N; ++i) scanf("%d", data+i);
        printf("Case %d:\n", t+1);
        solve();
    }
    return 0;
}

HDOJ 1754

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1754

题目大意

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。

思路

经典线段树题目,类似RMQ(Range Minimum Query)操作。

AC代码

/*************************************************************************
    > File Name: 1754.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-19 二 10:04:09 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <limits>
using namespace std;
const int MAXN = 2000000+5;
int data[MAXN];
int tree[MAXN << 1];
int N, M;
void build(int v, int l, int r) { // v树节点,[l, r)
    if(r - l == 1) {
        // printf("l:%d v:%d\n", l, v);
        tree[v] = data[l];
        return;
    }
    int chl = (v<<1)+1, chr = (v<<1)+2, m = (l+r) >> 1;
    build(chl, l, m);
    build(chr, m, r);
    tree[v] = max(tree[chl], tree[chr]);
}

void update(int v, int l, int r, int k, int a) { // 将k节点的数值更新为a
    // printf("v:%d l:%d r:%d k:%d a:%d\n", v, l, r, k, a);
    if(r - l == 1) {
        tree[v] = a;
    }
    else {
        int chl = (v<<1)+1, chr = (v<<1)+2, m = (l+r) >> 1;
        if(k < m) update(chl, l, m, k, a);
        else update(chr, m, r, k, a);
        tree[v] = max(tree[chl], tree[chr]);
    }
}

int query(int v, int l, int r, int L, int R) { // 查询[L, R)上的最大值
    if(L>=r || R<=l) return numeric_limits<int>::min();
    if(l>=L && r<=R) return tree[v];
    int chl = (v<<1)+1, chr = (v<<1)+2, m = (l+r) >> 1;
    int res = numeric_limits<int>::min();
    if(m>=L) res=max(res, query(chl, l, m, L, R)); // 左半部分还有
    if(m<=R) res=max(res, query(chr, m, r, L, R)); // 有半部分也有
    return res;
}


void solve() {
    build(0, 0, N);
    char op;
    int a, b;
    for(int i=0; i<M; ++i) {
        cin >> op >> a >> b;
        if(op == 'Q') cout << query(0, 0, N, a-1, b) << endl;
        if(op == 'U') update(0, 0, N, a-1, b);
    }

}

int main() {
#ifdef Oj
    freopen("1754.in", "r", stdin);
    // freopen("1754.out", "w",stdout);
#endif
    cin.sync_with_stdio(false);
    while(cin >> N >> M) {
        for (int i = 0; i < N; ++i) cin >> data[i];
        solve();
    }
    return 0;
}