codeforces 292E. Copying Data 线段树

By | 03月11日
Advertisement

题目链接

给两个长度为n的数组, 两种操作。

第一种, 给出x, y, k, 将a[x, x+k-1]这一段复制到b[y, y+k-1]。

第二种, 给出x, 输出b[x]的值。

线段树区间更新单点查询, 第一种操作, 就将线段树的[y, y+k-1]这一段赋值为i, i是第i个询问, 并将这个询问存到一个数组里。

第二种操作, 查询位置x处的值是多少, 做相应的修改就好..

感觉不是很难但还是写了好久

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int mod = 1e9+7;
const int inf = 1061109567;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
const int maxn = 1e5+5;
int sum[maxn<<2], cover[maxn<<2], a[maxn], b[maxn];
void pushDown(int rt) {
    if(cover[rt]) {
        if(cover[rt<<1]<cover[rt])
            cover[rt<<1] = cover[rt];
        if(cover[rt<<1|1]<cover[rt])
            cover[rt<<1|1] = cover[rt];
        cover[rt] = 0;
    }
}
void update(int L, int R, int val, int l, int r, int rt) {
    if(L<=l&&R>=r) {
        cover[rt] = val;
        return ;
    }
    pushDown(rt);
    int m = l+r>>1;
    if(L<=m)
        update(L, R, val, lson);
    if(R>m)
        update(L, R, val, rson);
}
int query(int p, int l, int r, int rt) {
    if(l == r) {
        return cover[rt];
    }
    pushDown(rt);
    int m = l+r>>1;
    if(p<=m)
        return query(p, lson);
    else
        return query(p, rson);
}
pll q[maxn];
int main()
{
    int n, m, x, y, k, sign;
    cin>>n>>m;
    for(int i = 1; i<=n; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i<=n; i++) {
        scanf("%d", &b[i]);
    }
    for(int i = 1; i<=m; i++) {
        scanf("%d", &sign);
        if(sign == 2) {
            scanf("%d", &x);
            int tmp = query(x, 1, n, 1);
            if(tmp!=0) {
                y = q[tmp].se;
                b[x] = a[q[tmp].fi+x-y];
            }
            printf("%d\n", b[x]);
        } else {
            scanf("%d%d%d", &x, &y, &k);
            q[i] = mk(x, y);
            update(y, y+k-1, i, 1, n, 1);
        }
    }
    return 0;
}

Similar Posts:

  • CodeForces 91B Queue【线段树】

    Queue Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u Submit Status Practice CodeForces 91B Description There are n walruses standing in a queue in an airport. They are numbered starting from the queue's tail: the 1-st w

  • [CF]292E. Copying Data 分块

    我想说这Round1是不是5道暴力啊!是不是暴力啊!是不是暴力!是不是! 不会写线段树,E在比赛的时候YY了一个分块一直WA,后来调的时候发现有个布尔值写反了?-- 效果还可以--不算快但也不至于特别慢,毕竟数据范围和CF评测机在这里摆着呢,空间很小而且还可以压-- /* 按sqrt(n)分块 如果两端在同一块内就直接暴力,否则分别暴力所在块到一端这一段再暴力它们之间的块 唯一要注意的是如果一块被标记是成段修改的,在暴力内部之前要先循环赋值一下并且去掉标记 */ #include <iostre

  • [codeforces] 762C - Two strings 线段树

    我想这题一定有不需要线段树的做法 但是比赛的时候时间紧迫也没有去想那么多觉得线段树可做直接上了 考虑留下来的区间,一定是左边一段右边一段(也可以只有左边或右边),我们需要找最长的这么两段,且这两段和A串匹配的LCS不能有交集. 线段树节点[l,r]值为y表示B串从左往右匹配LCS到A串的[l,r]区间,其中位置B串匹配到最长的长度为y,从左往右处理完之后再从右往左枚举B串长度和匹配到A串的位置,两者需要都没有交集. #include <iostream> #include <cstdio

  • Codeforces 356A Knight Tournament线段树区间覆盖

    传送门:  http://codeforces.com/contest/356/problem/A A. Knight Tournament time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output Hooray! Berl II, the king of Berland is making a knight tournament.

  • Codeforces Gym 100513F F. Ilya Muromets 线段树

    F. Ilya Muromets Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/gym/100513/problem/F Description I Ilya Muromets is a legendary bogatyr. Right now he is struggling against Zmej Gorynych, a dragon with n heads numbered from 1 to nf

  • set+线段树 Codeforces Round #305 (Div. 2) D. Mike and Feet

    题目传送门 1 /* 2 题意:对于长度为x的子序列,每个序列存放为最小值,输出长度为x的子序列的最大值 3 set+线段树:线段树每个结点存放长度为rt的最大值,更新:先升序排序,逐个添加到set中 4 查找左右相邻的位置,更新长度为r - l - 1的最大值,感觉线段树结构体封装不错! 5 详细解释:http://blog.csdn.net/u010660276/article/details/46045777 6 其实还有其他解法,先掌握这种:) 7 */ 8 #include <cstd

  • 【CodeForces】444C DZY Loves Colors 线段树

    C. DZY Loves Colors time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output DZY loves colors, and he enjoys painting. On a colorful day, DZY gets a colorful ribbon, which consists ofn units (they

  • CodeForces 46D Parking Pot(线段树区间更新)

    Parking Lot time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Nowadays it is becoming increasingly difficult to park a car in cities successfully. Let's imagine a segment of a street as long

  • 【codeforces】484E. Sign on Fence 可持久化线段树

    传送门:[codeforces]484E. Sign on Fence 题目分析:看了题解才会呢,感觉太巧妙了~ 先对高度从高到低排序,然后构造可持久化线段树,每个节点保存一个高度下对应区间的左连续最大1个数,右连续最大1个数,区间最长连续1个数,然后查询一个区间内最长连续1长度就是线段树区间合并操作.每次询问[L,R,W]就是二分询问的高度(每个高度是一棵线段树),然后看询问区间的连续1个数是否大于等于W,大于就调整上界,否则调整下界(下标小的高度大,这样处理的好处是二分可以很轻易的写出来,直

  • Codeforces Round #337 (Div. 2) E. Alphabet Permutations (线段树lazy 或 set)

    大致题意: 一个2e5的字符串STR,最多包含K个字符(K < 10) , 有Q个操作(<2e4) . 1. 把字符串[L, R]的字符修改成x 2. 给一个K个字符的某个排列s,询问最少重复次数的s连接而成的长串的子序列包含STR 思路1: 因为要修改STR,所以要对STR进行处理,然后要在logn以下的复杂度完成查询操作. 可以注意到最少重复的次数就是STR中相邻的两个字符(ch1, ch2) 在排列s中的位置是ch2在ch1之前,ch2和ch1必然是有两个s串组成.所以可以维护STR相邻

Tags: