2867 Where Are My Genes

問題概要

数列a1,a2,……,anに転置(i,j)を施すと、aiからajの部分が逆順になる。
元の数列は1,2,3,...,Nで、ここに与えられた転置を施すとき、元の数列のi番目の数字は何番目に来るか答えよ。

N≦50000,転置回数≦1000,求める数字の個数≦100を満たす。

解法

Nが大きいので転置を全てシミュレートするとTLE.
クエリが少ないので、クエリにある数だけ行き先を調べる。
i番目の数が転置(a,b)の影響を受けると、a+b-iの位置に来る。

ソースコード

int n,r,q,a[1000],b[1000],cs;
int main()
{
	while(scanf("%d",&n),n)
	{
		printf("Genome %d\n",++cs);
		scanf("%d",&r);
		rep(i,r)scanf("%d%d",a+i,b+i);
		scanf("%d",&q);
		rep(i,q)
		{
			int p; scanf("%d",&p);
			rep(j,r)if(a[j]<=p&&p<=b[j])p=a[j]+b[j]-p;
			printf("%d\n",p);
		}
	}
	return 0;
}