【NOI2018模拟4.2】program
程序员文章站
2022-06-03 15:15:50
...
Description:
题解:
做法真的很巧。
假设在开头加了无数个‘>’。
一直走,直到出了右边界。
记录f,g分别表示第一次从i-1到i的时间,和第一次i到i-1的时间。
这样对于一个区间[l..r]就可以求出进来的时间和出去的时间,相减就是答案。
f很好求 ,g可能还需要一个链表或者用线段树去求。
Code:
#include<cstdio>
#include<cstring>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
const int N = 100005, INF = 1e6;
int n, q, x, y; char s[N], a[N];
int la[N], ne[N], w, f;
int sum[N * 50][10], tot;
int g[N], h[N];
void de(int x) {
ne[la[x]] = ne[x], la[ne[x]] = la[x];
}
int t[N * 4], pl, pr, px;
void add(int i, int x, int y) {
if(y < pl || x > pr) return;
if(x >= pl && y <= pr) {t[i] = min(t[i], px); return;}
t[i + i] = min(t[i + i], t[i]);
t[i + i + 1] = min(t[i + i + 1], t[i]);
int m = x + y >> 1;
add(i + i, x, m); add(i + i + 1, m + 1, y);
}
void fi(int i, int x, int y) {
if(y < pl || x > pr) return;
if(x == y) {px = t[i]; return;}
t[i + i] = min(t[i + i], t[i]);
t[i + i + 1] = min(t[i + i + 1], t[i]);
int m = x + y >> 1;
fi(i + i, x, m); fi(i + i + 1, m + 1, y);
}
int main() {
freopen("program.in", "r", stdin);
freopen("program.out", "w", stdout);
memset(t, 127, sizeof t);
scanf("%d %d", &n, &q);
scanf("%s", s + 1);
ne[0] = 1; la[n + 1] = n;
fo(i, 1, n) la[i] = i - 1, ne[i] = i + 1;
w = 1, f = 0; s[0] = '>';
while(w <= n) {
tot ++;
fo(i, 0, 9) sum[tot][i] = sum[tot - 1][i];
if(!w) {
f = 0;
int u = ne[w];
if(u != 1 && !g[u]) g[u] = tot;
w = u;
continue;
}
if(s[w] >= '0' && s[w] <= '9') {
int u = f ? la[w] : ne[w];
if(f) {
pl = u + 1, pr = w; px = tot;
add(1, 1, n);
} else {
if(u != 1 && !g[u]) g[u] = tot;
}
sum[tot][s[w] - 48] ++;
if((-- s[w]) < 48) de(w);
w = u;
} else {
f = s[w] == '<';
int u = f ? la[w] : ne[w];
if(f) {
pl = u + 1, pr = w; px = tot;
add(1, 1, n);
} else {
if(u != 1 && !g[u]) g[u] = tot;
}
if(u > n) break;
if(!u || !(s[u] >= '0' && s[u] <= '9'))
de(w);
w = u;
}
}
fo(i, 2, n + 1) if(!g[i]) g[i] = INF;
fo(i, 1, n) {
px = INF;
pl = pr = i; fi(1, 1, n);
h[i] = px;
}
fo(ii, 1, q) {
scanf("%d %d", &x, &y);
fo(i, 0, 9) printf("%d ", sum[min(g[y + 1], h[x])][i] - sum[g[x]][i]);
printf("\n");
}
}