语文1（chin1）- 理理思维题解

Ynoi · 2018-09-29 18:45:22 · 题解

操作二将第xi到第yi个字符全部替换为ki

你想到了什么？

没错，推平一段区间，珂朵莉树基本操作。

珂朵莉树，优雅的暴力。

珂朵莉树模板题 题解中有对珂朵莉树的详细解释

珂朵莉就是把每个数字分为三元组l,r,v，表示a[l]~a[r]都是v

一般是用set实现，但我是用链表实现的。

之后就类似暴力的实现了

#include<bits/stdc++.h>
using namespace std;

#define MAXN 100005
char s[MAXN];
int n,m,nn;
struct aa
{
    int l,r,rr;
    char v;
}a[MAXN*30];
int c[50];

void wt()//调试用
{
    cout<<"-----------------\n";
    for(int i = n+1; i != 0; i = a[i].rr)
    {
        cout<<a[i].l<<" "<<a[i].r<<" "<<a[i].v<<"\n";
    }
    cout<<"-----------------\n";
}

void he()//合并
{
    for(int i = n+1; i != 0; i = a[i].rr)
    {
        while(a[i].v == a[a[i].rr].v && a[i].rr != 0)
        {
            a[i].r = a[a[i].rr].r;
            a[i].rr = a[a[i].rr].rr;
        }
    }
}

void rd()
{
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(int i = 1; i <= n; i ++)
    {
        if(s[i] <= 'Z' && s[i] >= 'A')
            s[i] = s[i] -'A' + 'a';
        a[i].l = i;
        a[i].r = i;
        a[i].v = s[i];
        if(i != n)
            a[i].rr = i+1;
    }
    a[n+1].rr = 1;
    a[n].rr = n+2;
    nn = n+2;
    he();
}

void fen(int i,int x)
{
    nn ++;
    a[nn].rr = a[i].rr;
    a[nn].r = a[i].r;
    a[nn].l = x;
    a[nn].v = a[i].v; 
    a[i].rr = nn;
    a[i].r = x-1;
} 

int paix(int l,int r,int p,char ch)//p代表操作
{
    memset(c,0,sizeof(c));
    for(int i = n+1; i != 0; i = a[i].rr)//先在将部分在处理区间内部分区间外的分离，方便之后操作
    {
        if(a[i].l < l && a[i].r >= l) fen(i,l); 
        if(a[i].l <= r && a[i].r > r) fen(i,r+1);
    }
    bool t = 0;
    int lp,rp;

    for(int i = n+1; i != 0; i = a[i].rr)
    {
        if(a[i].l >= l && a[i].r <= r)
        {
            if(p == 2)
                a[i].v = ch; 
            c[a[i].v-'a'] += a[i].r - a[i].l + 1;//统计每种字母出现次数
            t = 1;
        }
        else
        {
            if(t)
            {
                rp = i;
                break;
            }
            else lp = i;
        }
    }
    if(p == 2)
    {
        he();
        return 0;
    }
    if(p == 1)
    {
        he(); 
        return c[ch-'a'];
    }
    int u = a[lp].r,x = lp;
    for(int i = 0; i <= 26; i ++)//排序时重新插入
    if(c[i] != 0)
    {
        nn ++;
        a[x].rr = nn;
        x = nn;
        a[nn].v = 'a' + i;
        a[nn].l = u+1;
        a[nn].r = u + c[i];
        u += c[i];
    }

    a[x].rr = rp;
    he();
    return 0;
} 


int main()
{

    rd();
    for(int i = 1; i <= m; i ++)
    {
        int l,r,opt;
        string s;
        scanf("%d",&opt);
        if(opt == 1)
        {
            cin >> l >> r >> s;
            if(s[0] < 'a')
                s[0] = s[0]  - 'A'+ 'a';
            cout<<paix(l,r,1,s[0])<<"\n";

        }
        if(opt == 2)
        {
            cin >> l >> r >> s;
            if(s[0] < 'a')
                s[0] = s[0] - 'A' +  'a';
            paix(l,r,2,s[0]);
        }
        if(opt == 3)
        {
            cin >> l >> r;
            paix(l,r,0,'a');
        }
    }
    return 0;
}