[codeforces] 498D Traffic Jams in th Land

原题

简单的线段树问题。

对于题目中，a[i]的范围是2_{6，我们仔细思考可以得出第0秒和第60秒是一样的（因为2}6的最小公倍数是60,），然后我们可以建一个线段树，里面记录0~59秒时刻开始通过这段所需要的时间。（如果一定要说这是60棵线段树也不是不可以……）

#include<cstdio>

#define N 100010

using namespace std;

int n,a[N],q,x,y;

char j;

struct hhh

{

    int l,r,dt[65];

}tre[N*4];

int read()

{

    int ans=0,fu=1;

    char j=getchar();

    for (;(j<'0' || j>'9') && j!='-';j=getchar()) ;

    if (j=='-') fu=-1;

    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';

    return ans*fu;

}

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

{

    tre[i].l=l;

    tre[i].r=r;

    if (l==r)

    {

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

	if (!t || t%a[l]==0) tre[i].dt[t]=2;

	else tre[i].dt[t]=1;

	return ;

    }

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

    build(i*2,l,mid);

    build(i*2+1,mid+1,r);

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

	tre[i].dt[t]=tre[i*2].dt[t]+tre[i*2+1].dt[(t+tre[i*2].dt[t])%60];

}

void modify(int i,int x)

{

    if (tre[i].l==tre[i].r && x==tre[i].l)

    {

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

	if (t%a[x]==0) tre[i].dt[t]=2;

	else tre[i].dt[t]=1;

	return ;

    }

    int mid=(tre[i].l+tre[i].r)>>1;

    if (x<=mid) modify(i*2,x);

    else modify(i*2+1,x);

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

	tre[i].dt[t]=tre[i*2].dt[t]+tre[i*2+1].dt[(t+tre[i*2].dt[t])%60];

}

int query(int i,int l,int r,int t)

{

    if (tre[i].l==l && tre[i].r==r) return tre[i].dt[t%60];

    int mid=(tre[i].l+tre[i].r)>>1;

    if (r<=mid) return query(i*2,l,r,t);

    if (l>mid) return query(i*2+1,l,r,t);

    else

    {

	int p=query(i*2,l,mid,t);

	p+=query(i*2+1,mid+1,r,(t+p)%60);

	return p;

    }

}

int main()

{

    n=read();

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

    build(1,1,n);

    q=read();

    while (q--)

    {

	j=getchar();

	x=read();

	y=read();

	if (j=='C') a[x]=y,modify(1,x);

	else printf("%d\n",query(1,x,y-1,0));

    }

    return 0;

}

巴特西

[codeforces] 498D Traffic Jams in th Land

原题

最新文章

热门文章