欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【NOI2018模拟4.2】program

程序员文章站 2022-06-03 15:15:50
...

Description:

【NOI2018模拟4.2】program

题解:

做法真的很巧。

假设在开头加了无数个‘>’。

一直走,直到出了右边界。

记录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");
    }
}
相关标签: 信息学 greedy