# P3514题解()-其他

## P3514题解()

SPJ对于格式的要求较为严格。对于每个询问后，应紧跟一个换行符。在最后一次输出你的答案以及一个换行符后不应有任何输出。

### 题解

``````#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 2000050
#define scanf scanf_s
struct node {
int l, r;
}ans[N];
int val[N], n, m, q, s1[N], s2[N], pos1, pos2;
void dfs(int l, int r, int k) {
if (ans[k].l)return;
if (l > r)return;
ans[k] = { l,r };
if (val[l] == 2) {
dfs(l + 1, r, k - 2);
}
else if (val[r] == 2) {
dfs(l, r - 1, k - 2);
}
else dfs(l + 1, r - 1, k - 2);
}
void init() {
memset(ans, 0, sizeof ans);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
char x;
cin >> x;
if (x == 'T')val[i] = 2;
else val[i] = 1;
}
for (int i = 1; i <= n; i++)s1[i] = s1[i - 1] + val[i];
for (int i = n; i >= 1; --i)s2[i] = s2[i + 1] + val[i];
for (int i = 1; i <= n; i++)if (val[i] == 1) { pos1 = i + 1; break; }
for (int i = n; i > 0; --i)if (val[i] == 1) { pos2 = i - 1; break; }
if (s2[pos1] > s1[pos2]) { dfs(pos1, n, s2[pos1]); }
else { dfs(1, pos2, s1[pos2]); }
dfs(1, n, s1[n]);
}
int main() {
init();
while (m--) {
int k;
scanf("%d", &k);
if (ans[k].l == 0)puts("NIE");
else printf("%d %d\n", ans[k].l, ans[k].r);
}
return 0;
}
``````
————————

SPJ对于格式的要求较为严格。对于每个询问后，应紧跟一个换行符。在最后一次输出你的答案以及一个换行符后不应有任何输出。

### 题解

``````#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 2000050
#define scanf scanf_s
struct node {
int l, r;
}ans[N];
int val[N], n, m, q, s1[N], s2[N], pos1, pos2;
void dfs(int l, int r, int k) {
if (ans[k].l)return;
if (l > r)return;
ans[k] = { l,r };
if (val[l] == 2) {
dfs(l + 1, r, k - 2);
}
else if (val[r] == 2) {
dfs(l, r - 1, k - 2);
}
else dfs(l + 1, r - 1, k - 2);
}
void init() {
memset(ans, 0, sizeof ans);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
char x;
cin >> x;
if (x == 'T')val[i] = 2;
else val[i] = 1;
}
for (int i = 1; i <= n; i++)s1[i] = s1[i - 1] + val[i];
for (int i = n; i >= 1; --i)s2[i] = s2[i + 1] + val[i];
for (int i = 1; i <= n; i++)if (val[i] == 1) { pos1 = i + 1; break; }
for (int i = n; i > 0; --i)if (val[i] == 1) { pos2 = i - 1; break; }
if (s2[pos1] > s1[pos2]) { dfs(pos1, n, s2[pos1]); }
else { dfs(1, pos2, s1[pos2]); }
dfs(1, n, s1[n]);
}
int main() {
init();
while (m--) {
int k;
scanf("%d", &k);
if (ans[k].l == 0)puts("NIE");
else printf("%d %d\n", ans[k].l, ans[k].r);
}
return 0;
}
``````