CF498D：Traffic Jams in the Land—

https://vjudge.net/problem/CodeForces-498D

http://codeforces.com/problemset/problem/498/D

题面描述：

一些国家由（n + 1）个城市组成，位于一条直路上。我们用连续的整数从1到n + 1按照高速公路上出现的顺序对城市进行编号。因此，城市由高速公路的n段连接起来，第i段连接城市i和i + 1。高速公路的每一段都与一个正整数ai相关联 - 表示何时交通拥堵期出现在该段上。

为了从城市x到城市y（x <y），一些司机使用以下策略。

最初驾驶员在城市x，当前时间t等于0。在驾驶员抵达城市之前，他会采取以下行动：

1.如果当前时间t是ax的倍数，那么高速公路号x的段现在有交通问题，驾驶员在当前城市停留一个单位时间（当前t = t + 1）。

2.如果当前时间t不是ax的倍数，那么高速公路号x的段现在是畅通的，驾驶员使用一个单位时间移动到城市x + 1（当前t = t + 1且x = x + 1）。

你正在开发一个新的交通控制系统。您要连续处理两种类型的q查询：

A：我们应用上面描述的策略，确定从城市x到城市y（x <y）之后的时间t的最终值。请注意，对于每个查询t初始值为0。

C：用值y替换出现在段号x上的堵塞时段（令ax = y）。

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

Output

这道题还是不是那么好想的……

我们需要发现一个性质：对于0s和60s来说，我们只要走相同的路得到的时间%60都是一样的。

（原因很简单，2-6最小公倍数为60）

所以我们开线段树tree[i][j]表示i区间从js（0<=j<60）开始从头走到尾的最终时间。

build的时候公式如下：

tree[a][i]=tree[a*2+1][tree[a*2][i]%tmax]+tree[a*2][i]/tmax*tmax;

gai的时候和build差不多。

询问的话……看代码吧。

（祝贺60棵线段树AC第一道CF题）

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<iostream>

using namespace std;

typedef long long ll;

inline int read(){

    int X=,w=; char ch=;

    while(ch<''||ch>'') {if(ch=='-') w=-;ch=getchar();}

    while(ch>=''&&ch<='') X=(X<<)+(X<<)+ch-'',ch=getchar();

    return X*w;

}

const int tmax=;

int tree[][tmax];

int b[];

void build(int a,int l,int r){

    if(l==r){

   　　 for(int i=;i<tmax;i++){

    　　    if(i%b[l])tree[a][i]=i+;

    　　    else tree[a][i]=i+;

   　　 }

    return;

    }

    int mid=(l+r)>>;

    build(a*,l,mid);

    build(a*+,mid+,r);

    for(int i=;i<tmax;i++){

   　　 tree[a][i]=tree[a*+][tree[a*][i]%tmax]+tree[a*][i]/tmax*tmax;

    }

    return;

}

int check(int a,int l,int r,int l1,int r1,int t){

    if(l>r1||r<l1)return t;

    if(l1<=l&&r<=r1){

    　　return tree[a][t%tmax]+t/tmax*tmax;

    }

    int mid=(l+r)>>;

    int k1=check(a*,l,mid,l1,r1,t);

    int k2=check(a*+,mid+,r,l1,r1,k1);

    return k2;

}

void gai(int a,int l,int r,int x,int y){

    if(x<l||r<x)return;

    if(l==x&&x==r){

   　　 b[l]=y;

       for(int i=;i<tmax;i++){

     　　   if(i%b[l])tree[a][i]=i+;

    　　    else tree[a][i]=i+;

   　　 }

    　　return;

    }

    int mid=(l+r)>>;

    gai(a*,l,mid,x,y);

    gai(a*+,mid+,r,x,y);

    for(int i=;i<tmax;i++){

    　　tree[a][i]=tree[a*+][tree[a*][i]%tmax]+tree[a*][i]/tmax*tmax;

    }

    return;

}

int main(){

    int n=read();

    for(int i=;i<=n;i++){

    　　b[i]=read();

    }

    build(,,n);

    int q=read();

    for(int i=;i<=q;i++){

    　　char c;

  　　  cin>>c;

   　　 int x=read();

    　　int y=read();

   　　 if(c=='A'){

      　　  printf("%d\n",check(,,n,x,y-,));

 　　   }else{

       　　 gai(,,n,x,y);

 　　   }

    }

    return ;

}

巴特西

CF498D：Traffic Jams in the Land——题解

最新文章

热门文章