「CF498D」Traffic Jams in the Land

2014年12月25日4,6011

Some country consists of (n + 1) cities, located along a straight highway. Let’s number the cities with consecutive integers from 1 to n + 1 in the order they occur along the highway. Thus, the cities are connected by n segments of the highway, thei-th segment connects cities number i and i + 1. Every segment of the highway is associated with a positive integer a_i > 1 — the period of traffic jams appearance on it.

In order to get from city x to city y (x < y), some drivers use the following tactics.

Initially the driver is in city x and the current time t equals zero. Until the driver arrives in city y, he perfors the following actions:

if the current time t is a multiple of a_x, then the segment of the highway number x is now having traffic problems and the driver stays in the current city for one unit of time (formally speaking, we assign t = t + 1);
if the current time t is not a multiple of a_x, then the segment of the highway number x is now clear and that’s why the driver uses one unit of time to move to city x + 1 (formally, we assign t = t + 1 and x = x + 1).

You are developing a new traffic control system. You want to consecutively process q queries of two types:

determine the final value of time t after the ride from city x to city y (x < y) assuming that we apply the tactics that is described above. Note that for each query t is being reset to 0.
replace the period of traffic jams appearing on the segment number x by value y (formally, assign a_x = y).

Write a code that will effectively process the queries given above.

Input

The first line contains a single integer n (1 ≤ n ≤ 10⁵) — the number of highway segments that connect the n + 1 cities.

The second line contains n integers a₁, a₂, …, a_n (2 ≤ a_i ≤ 6) — the periods of traffic jams appearance on segments of the highway.

The next line contains a single integer q (1 ≤ q ≤ 10⁵) — the number of queries to process.

The next q lines contain the descriptions of the queries in the format c, x, y (c — the query type).

If c is character ‘A‘, then your task is to process a query of the first type. In this case the following constraints are satisfied: 1 ≤ x < y ≤ n + 1.

If c is character ‘C‘, then you need to process a query of the second type. In such case, the following constraints are satisfied: 1 ≤ x ≤ n, 2 ≤ y ≤ 6.

Output

For each query of the first type output a single integer — the final value of time t after driving from city x to city y. Process the queries in the order in which they are given in the input.

Sample test(s)

input

10
2 5 3 2 3 5 3 4 2 4
10
C 10 6
A 2 6
A 1 3
C 3 4
A 3 11
A 4 9
A 5 6
C 7 3
A 8 10
A 2 5

2 5 3 2 3 5 3 4 2 4

C 10 6

A 2 6

A 1 3

C 3 4

A 3 11

A 4 9

A 5 6

C 7 3

A 8 10

A 2 5

output

题解

显然这是数据结构题。。。

线段树可以解决，发现y<=6，所以只要在线段树每个节点记录t[x],res[x]表示从x（mod 60）时刻开始，在这一段的堵车时间，以及最后时刻（mod 60）

然后合并比较显然。。

#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#define ll long long
#define mod 1000000007
#define inf 1000000000
using namespace std;
int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int a[100005];
struct seg{
    int l,r,t[60],res[60];
    seg(){}
    seg(int _l,int _r,int x):l(_l),r(_r){
        for(int i=0;i<60;i++)
            if(i%x==0)t[i]=1,res[i]=2;
            else t[i]=0,res[i]=1;
    }
}t[400005];
seg merge(seg a,seg b)
{
    seg t;
    t.l=a.l;t.r=b.r;
    for(int i=0;i<60;i++)
    {
        t.t[i]=a.t[i]+b.t[a.res[i]];
        t.res[i]=(a.res[i]+b.res[a.res[i]%60])%60;
    }
    return t;
}
void build(int k,int l,int r)
{
    t[k].l=l;t[k].r=r;
    if(l==r){t[k]=seg(l,r,a[l]);return;}
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    t[k]=merge(t[k<<1],t[k<<1|1]);
}
seg query(int k,int x,int y)
{
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(x==l&&y==r)return t[k];
    if(y<=mid)return query(k<<1,x,y);
    else if(x>mid)return query(k<<1|1,x,y);
    else return merge(query(k<<1,x,mid),query(k<<1|1,mid+1,y));
}
void change(int k,int x,int val)
{
    int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(l==r){t[k]=seg(l,r,val);return;}
    if(x<=mid)change(k<<1,x,val);
    else change(k<<1|1,x,val);
    t[k]=merge(t[k<<1],t[k<<1|1]);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    m=read();
    char opt[4];
    int x,y;
    while(m--)
    {
        scanf("%s",opt);
        x=read();y=read();
        if(opt[0]=='C')change(1,x,y);
        else printf("%d\n",query(1,x,y-1).t[0]+y-x);
    }
    return 0;
}

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<set>

#define ll long long

#define mod 1000000007

#define inf 1000000000

using namespace std;

int read()

{

int f=1,x=0;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int a[100005];

struct seg{

int l,r,t[60],res[60];

seg(){}

seg(int _l,int _r,int x):l(_l),r(_r){

for(int i=0;i<60;i++)

if(i%x==0)t[i]=1,res[i]=2;

else t[i]=0,res[i]=1;

}

}t[400005];

seg merge(seg a,seg b)

{

seg t;

t.l=a.l;t.r=b.r;

for(int i=0;i<60;i++)

{

t.t[i]=a.t[i]+b.t[a.res[i]];

t.res[i]=(a.res[i]+b.res[a.res[i]%60])%60;

}

return t;

}

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;

if(l==r){t[k]=seg(l,r,a[l]);return;}

int mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

t[k]=merge(t[k<<1],t[k<<1|1]);

}

seg query(int k,int x,int y)

{

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(x==l&&y==r)return t[k];

if(y<=mid)return query(k<<1,x,y);

else if(x>mid)return query(k<<1|1,x,y);

else return merge(query(k<<1,x,mid),query(k<<1|1,mid+1,y));

}

void change(int k,int x,int val)

{

int l=t[k].l,r=t[k].r,mid=(l+r)>>1;

if(l==r){t[k]=seg(l,r,val);return;}

if(x<=mid)change(k<<1,x,val);

else change(k<<1|1,x,val);

t[k]=merge(t[k<<1],t[k<<1|1]);

}

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i]=read();

build(1,1,n);

m=read();

char opt[4];

int x,y;

while(m--)

{

scanf("%s",opt);

x=read();y=read();

if(opt[0]=='C')change(1,x,y);

else printf("%d\n",query(1,x,y-1).t[0]+y-x);

}

return 0;

}

« 「POJ3237」Tree 「codechefTASTRMAT」String Matching »

邹雨恒

对不起我坑了你

hzwer.com _ Home | http://hzwer.com

「CF498D」Traffic Jams in the Land

分类目录

热门文章

Myfriends

近期评论