记录编号	519547	评测结果	AAAAAAAAAA
题目名称	AAAE(无题面)	最终得分	100
用户昵称	胡嘉兴	是否通过	通过
代码语言	C++	运行时间	4.345 s
提交时间	2018-11-01 18:05:33	内存使用	51.81 MiB

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
const int N = 3e6+7, maxlog = 23;
char s[N], ans[N];
int n, k, a[N], p[N], l[N], r[N];
void add(int x, int d)
{
	for(int i = x; i <= k; i += lowbit(i))
	{
		a[i] += d;
	}
	return;
}
int seek(int x)
{
	int sum = 0, ret = 0;
	for(int i = maxlog; i >= 0; i--)
	{
		if(ret+(1<<i)>k)
		{
			continue;
		}
		if(sum+a[ret+(1<<i)]<x)
		{
			ret += (1<<i);
			sum += a[ret];
		}
	}
	return ret+1;
}
char find(int x)
{
	return ans[x] ? ans[x] : ans[x] = find(p[x]);
}
int check(int l, int j, int len)
{
 	if(l%2)
   	{
		if(len%2)
		{
            if(j<=len/2+1)
		    {
			    return j*2-1+l-1;
		    }
		    else
		    {
				return (j-len/2-1)*2+l-1;
			}
		}
		else
		{
			if(j<=len/2)
			{
				return l-1+j*2-1;
			}
			else
			{
				return l-1+(j-len/2)*2;
			}
		}
	}
	else
	{
	 	if(len%2)
		{
			if (j<=len/2)
			{
     			return l-1+j*2;
     		}
			else
			{
     			return l-1+(j-len/2)*2-1;
     		}
		}
		else
		{
			if(j<=len/2)
			{
  	  			return l-1+j*2;
			}
			else
			{
				return l-1+(j-len/2)*2-1;
			}
		}
	}
}
int main()
{
	freopen("AAAE.in", "r", stdin);
    freopen("AAAE.out", "w", stdout);
	scanf("%s%d%d", s+1, &k, &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d%d", &l[i], &r[i]);
    }
    for(int i = 1; i <= k; i++)
    {
		a[i] = lowbit(i);
	}
    int tot = k;
    for(int i = n; i >= 1; i--)
    {
    	int fl = l[i], fr = r[i], len = r[i]-l[i]+1, cnt = 0;
    	for(int j = fr+1, k = 1; k <= len&&j <= tot; j++, k++)
    	{
    		++cnt;
    		int pos = seek(fr+1);
    		add(pos, -1);
    		int tmp = seek(check(fl, k, len));
    		p[pos] = tmp;
    	}
    	tot -= cnt;
    }
    tot = 0;
    for(int i = 1; i <= k; i++)
    {
    	if(!ans[i])
    	{
    		if(!p[i])
    		{
    			ans[i] = s[++tot];
    		}
    		else
    		{
    			ans[i] = find(i);
    		}
    	}
    }
    ans[k+1] = '\0';
    printf("%s\n", ans+1);
	return 0;
}