財神娛樂首存即享優惠回饋唷~詳情請進👉

【數據布局】莫隊(中國 老虎機二)

捕魚達人簽到

  本日的內容是帶修莫隊。

例題:P1903 [國度集訓隊]數顏色 / 維護行列步隊

標題描寫

墨墨購買了一套N支彩色畫筆(個中有些顏色可能雷同),擺成一排,你必要歸答墨墨的發問。墨墨會向你發布以下指令:

一、 Q L R代表扣問你從第L支畫筆到第R支畫筆中共有幾種不同顏色的畫筆。

2、 R P Col 把第P支畫筆替代為顏色Col。

為了知足墨墨的要求,你曉得你必要干甚么了嗎?

輸出格局

第1行兩個整數N,M,分手代表初始畫筆的數目和墨墨會做的工作的個數。

第2行N個整數,分手代表初始畫筆排中第i支畫筆的顏色。

第3行到第2+M行,每行分手代表墨墨會做的一件工作,格局見題干部香港六合彩资料門。

輸入格局

關于每一個Query的扣問,你必要在對應的行中給出一個數字,代表第L支畫筆到第R支畫筆中共有幾種不同顏色的畫筆。

輸出輸入樣例

輸出 #1

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

輸入 #1

4
4
3
4

申明/提醒

關于100%的數據,N≤50000,M≤50000,一切的輸出數據中浮現的一切整數均大于即是1且不跨越10^6。

本題可能稍微卡常數

泉源:bzoj2120

本題數據為洛谷自造數據,使用CYaRon耗時5分鐘實現數據建造。


帶修莫隊

  莫隊是一種很神奇的離線算法。可以辦理區間上的成績,經由過程排序以及對扣問分塊來優化暴力。

  平凡的莫隊標題都是給定的序列,賡續的扣問。

  那末若是在扣問中混合了一些點竄操作,莫隊還能做嗎?

  謎底當然是可以的。

  歸顧一下莫隊的完成要領:

    1.提早預處置

    2.扣問分塊排序

    3.雙指針挪移求解。

  獨一會由于點竄而發生轉變的操作便是3操作。

  可以發明:當浮現了點竄操作以后,我當前扣問處置的區間可能就不是咱們原先要找的區間了。

  那末怎么辦呢?

  自創一下可持久化線段樹的思惟:韶光歸溯。

  咱們可以先把帶修莫隊當做一般的莫隊來做,做完以后若是發明時間對不上就韶光倒流。

  準確的說是:思量兩個時間點的操作之間的價值。

  這么說來,只需在平凡莫隊的一堆 while 輪回前面再加兩個就OK。

 while(now<q[i].t)
     change(++now);
 while(now>q[i].t)
     change(now--);    

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int N=50005;
int col[N],n,m,sum[1000005],be[N];
int fans,qnum,cnum,ans[N];

struct qs{
    int l,r,t,id;
}q[N];
struct cs{
    int x,i;
}c[N];

bool cmp(qs x,qs y) {
    if(be[x.l]!=be[y.l])
        return x.l<y.l;
    if(be[x.r]!=be[y.r])
        return x.r<y.r;
    return x.t<y.t;
}

void upd1(int x) {
    if(!sum[col[x]])
        ++fans;
    ++sum[col[x]];
    return;
}

void upd2(int x) {
    --sum[col[x]];
    if(!sum[col[x]])
        --fans;
    return;
}

int l,now;

void change(int x) {
    if(c[x].i<=r&&c[x].i>=l) {
        --sum[col[c[x].i]];
        if(!sum[col[c[x].i]])
            --fans;
        if(!sum[c[x].x])
            ++fans;
        ++sum[c[x].x];
    }
    swap(c[x].x,col[c[x].i]);
    return;
}

int m增加偏財運的方法ain()
{
    cin>>n>>m;
    int xx=pow(n,2.0/3.0);
    char opt; 
    for(int i=1;i<=n;i++) {
        cin>>col[i];
        be[i]=i/xx+1;
    }
    for(int i=1;i<=m;i++) {
        cin>>opt;
        if(opt==‘Q‘) {
            ++qnum;
            cin>>q[qnum].l>>q[qnum].r;
            q[qnum].t=cnum;
            q[qnum].id=qnum;
        }
        else {
            ++cnum;
            cin>>c[cnum].i>>c[cnum].x;
        }
    }
    sort(q+1,q+qnum+1,cmp);
    l=r=fans=now=0;
    for(int i=1;i<=qnum;i++) {
        while(l<q[i].l)
            upd2(l++);
        while(l>q[i].l)
            upd1(--l);
        while(r>q[i].r)
            upd2(r--);
        while(r<q[i].r)
            upd1(++r);
        while(now<q[i].t)
            change(++now);
        while(now>q[i].t)
            change(now--);
        ans[q[i].id]=fans;
    }
    for(int i=1;i<=qnum;i++)
        cout<<ans[i]<<endl;
    return 0;
}

數顏色六合彩版路

?


雙倍履歷?CF940F Machine Learning

捕魚達人-遊戲

【免責聲明】本站內容轉載自互聯網,其相關談吐僅代表作者小我私家概念盡非權勢巨子,不代表本站態度。如您發明內容存在版權成績,請提交相關鏈接至郵箱:,咱們將實時予以處置。