D. Guess The String

Problem summary

The Jury chosen a stringS consisting of n characters; each character of S is a lowercase Latin letter.

You may ask query in two types:

1. 1 i - query for the letterSi
2. 2 l r - query the size of character set of Sl,Sl+1,......,Sr

You are allowed to ask no more than 26 queries of the first type, and no more than 6000 queries of the second type.

Output the final S you found in ! S

Sample Input

5
4
u
2
g
e
s
1

Sample Ouput

? 2 1 5
? 1 2
? 2 1 2
? 1 1
? 1 3
? 1 4
? 2 4 5
! guess

Tourial

First, it is easy to recognize that first type of operate is to find the letters which are first time appear.

so, the first question is when we construct string, how to know whether the character has ever appeared.

We define f(x, y) represent the size of the charater-set in range [x, y].

We know that 2nd op tell us the size of the charater-set. So abviously we solve the question by perform 2nd op. If we construct the string in order, we query f(1, x) and f(1, x - 1), if f(1, x) bigger than f(1, x -1), means s[x] never appeared in s[1] - s[x - 1]. and then we perform 1st op to judge the character of s[x].

After that, the new question appeares: how to know the character X, if f(1, x) equals to f(1, x - 1).

Assume we know every charater in s[1] to s[x - 1], and s[x] has appeared in this range. limited by the perform times of 2nd op. we can only perform 6 times max for s[x]. Because We construct the answer string in order, the monotonicity implict in problem is: from left to right, the longer the string, the monotoncically increasing the charater-set’s size. Base on it, we could use binary search to guess s[x].

We record every character’s last position. We already know f(lastPos[mid], x - 1), so if f(mid, x) equals to f(mid, x - 1), means s[x] last appeared in rangelastPos[s[mid]]to (x - 1). Through the binary search, we could find s[x] last appeared position, and easily to konw s[x].

Code

//CPP
void solveD(){
	int n;
	scanf("%d", &n);
	char s[n + 5];

	s[n + 1] = '\0';
	printf("? 1 1\n");
	fflush(stdout);
	scanf(" %c", &s[1]);
	PIC lastPos[26];
	int tot = 1;
	lastPos[tot] = PIC(1, s[1]);

	for(int i = 2; i <= n; ++i){
		printf("? 2 1 %d\n", i);
		fflush(stdout);
		int sz;
		scanf(" %d", &sz);
		if(sz != tot) {
			printf("? 1 %d\n", i);
			fflush(stdout);
			scanf(" %c", &s[i]);
			lastPos[++tot] = PIC(i, s[i]);
			continue;
		}
		sort(lastPos + 1, lastPos + tot + 1);
		int l = 1, r = tot;
		int ans = 0;
		while(l <= r){
			int mid = l + r >> 1;
			printf("? 2 %d %d\n", lastPos[mid].first, i);
			fflush(stdout);
			scanf(" %d", &sz);
			if(sz == tot - mid + 1) ans = mid, l = mid + 1;
			else r = mid - 1;
		}
		s[i] = lastPos[ans].second;
		lastPos[ans].first = i;
	}
	printf("! %s\n", s + 1);
	fflush(stdout);
}