absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
Codeforces 52 C 解题报告
321 C 解题报告

CF 292E 解题报告

absi2011 posted @ Jan 10, 2016 12:49:23 AM in 刷题记录 with tags CF 线段树 , 328 阅读

链接:http://www.codeforces.com/contest/292/problem/E

题意:

有两个数组a和b

每次进行两种操作

1,将a[x...x+k-1]赋值给b[y...y+k-1]

2,单点询问

算法:线段树

还是一样的线段树,只是维护的稍微麻烦一些而已...

和52C差不多吧..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[200005];
int val[1<<18];
void push_down(int num,int l,int r)
{
    if (val[num]==-1)
    {
        return;
    }
    int mid=(l+r)/2;
    val[num*2+1]=val[num];
    val[num*2+2]=val[num]+mid-l;
    val[num]=-1;
}
void change(int num,int l,int r,int l0,int r0,int k)
{
    if ((l0<=l)&&(r<=r0))
    {
        val[num]=k+(l-l0);
        return;
    }
    push_down(num,l,r);
    int mid=(l+r)/2;
    if (l0<mid)
    {
        change(num*2+1,l,mid,l0,r0,k);
        if (mid<r0)
        {
            change(num*2+2,mid,r,l0,r0,k);
        }
    }
    else if (mid<r0)
    {
        change(num*2+2,mid,r,l0,r0,k);
    }
}
int query(int num,int l,int r,int t)
{
    if (l==r-1)
    {
        return val[num];
    }
    push_down(num,l,r);
    int mid=(l+r)/2;
    if (t<mid)
    {
        return query(num*2+1,l,mid,t);
    }
    else
    {
        return query(num*2+2,mid,r,t);
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<n+n;i++)
    {
        scanf("%d",&a[i]);
    }
    memset(val,-1,sizeof(val));
    change(0,0,n,0,n,n);
    for (i=0;i<m;i++)
    {
        int oper;
        scanf("%d",&oper);
        if (oper==1)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            x--;
            y--;
            change(0,0,n,y,y+z,x);
        }
        else
        {
            int x;
            scanf("%d",&x);
            x--;
            printf("%d\n",a[query(0,0,n,x)]);
        }
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter