洛谷P2464 [SDOJ2008]郁闷的小J-白红宇

洛谷P2464 [SDOJ2008]郁闷的小J

阅读量：4477 次

发布时间：2019-06-08

本文共 4278 字，大约阅读时间需要 14 分钟。

题目描述

小J是国家图书馆的一位图书管理员，他的工作是管理一个巨大的书架。虽然他很能吃苦耐劳，但是由于这个书架十分巨大，所以他的工作效率总是很低，以致他面临着被解雇的危险，这也正是他所郁闷的。

具体说来，书架由N个书位组成，编号从1到N。每个书位放着一本书，每本书有一个特定的编码。

小J的工作有两类：

1.图书馆经常购置新书，而书架任意时刻都是满的，所以只得将某位置的书拿掉并换成新购的书。

2.小J需要回答顾客的查询，顾客会询问某一段连续的书位中某一特定编码的书有多少本。

例如，共5个书位，开始时书位上的书编码为1，2，3，4，5

一位顾客询问书位1到书位3中编码为“2”的书共多少本，得到的回答为：1

一位顾客询问书位1到书位3中编码为“1”的书共多少本，得到的回答为：1

此时，图书馆购进一本编码为“1”的书，并将它放到2号书位。

一位顾客询问书位1到书位3中编码为“2”的书共多少本，得到的回答为：0

一位顾客询问书位1到书位3中编码为“1”的书共多少本，得到的回答为：2

……

你的任务是写一个程序来回答每个顾客的询问。

输入输出格式

输入格式：

第一行两个整数N，M，表示一共N个书位，M个操作。

接下来一行共N个整数数A1,A2…AN，Ai表示开始时位置i上的书的编码。

接下来M行，每行表示一次操作，每行开头一个字符

若字符为‘C’，表示图书馆购进新书，后接两个整数A(1<=A<=N)，P，表示这本书被放在位置A上，以及这本书的编码为P。

若字符为‘Q’，表示一个顾客的查询，后接三个整数A，B，K(1<=A<=B<=N)，表示查询从第A书位到第Ｂ书位（包含Ａ和Ｂ）中编码为Ｋ的书共多少本。

输出格式：

对每一个顾客的查询，输出一个整数，表示顾客所要查询的结果。

输入输出样例

输入样例#1：

5 51 2 3 4 5Q 1 3 2Q 1 3 1C 2 1Q 1 3 2Q 1 3 1

输出样例#1：

说明

对于40%的数据，1<=N,M<=5000

对于100%的数据，1<=N,M<=100000

对于100%的数据，所有出现的书的编码为不大于2147483647的正数。

题解

我这里的“种类”就是原题的“编码”。。。

对每种书建立一棵平衡树（我用无旋treap），然后一开始往每个平衡树里插坐标（当然要有序插入）。

开一个数组记录每个位置上书的种类。

对于'C'操作，找到这个位置上书的种类，然后在对应平衡树上删去这个坐标。再记录新的种类，在对应平衡树上新增这个坐标。每个平衡树记录的坐标都应该是有序的。

对于'Q'操作，答案是对应平衡树上的B的排名减去(A-1)的排名，所以剩下的区间就是\([A,B]\)。

输入保证书的种类\(<=2^{31}-1\)，所以要离散化。。。我只会map。。。而且懒得打离线了。。。所以边读入边离散化。。。离散化在ins函数中体现，及每读入一次就插入（有的话当然不插入）

Code

// It is made by XZZ#include
    
     #include
     
      #include
      #define Fname "lg2464"using namespace std;#define rep(a,b,c) for(rg int a=b;a<=c;a++)#define drep(a,b,c) for(rg int a=b;a>=c;a--)#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])#define il inline#define rg register#define vd void#define pr pair
       
        #define mp make_pairtypedef long long ll;il int gi(){    rg int x=0,f=1;rg char ch=getchar();    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();    return x*f;}int seed=666;il int Rand(){return seed=seed*19260817ll%2147483647;}typedef struct node* point;point null;struct node{    int pos,rand,size;    point ls,rs;    node(int _pos){pos=_pos,rand=Rand(),size=1,ls=rs=null;}    il vd reset(){size=ls->size+rs->size+1;}    il vd del(){if(this!=null)ls->del(),rs->del(),delete this;}};point root[100001];int Book[100001];il point merge(point a,point b){    if(a==null)return b;    if(b==null)return a;    if(a->rand
        
         rand){a->rs=merge(a->rs,b),a->reset();return a;}    else{b->ls=merge(a,b->ls),b->reset();return b;}}il pr split(point now,int num){    if(now==null)return mp(null,null);    point ls=now->ls,rs=now->rs;    if(now->ls->size==num){now->ls=null,now->reset();return mp(ls,now);}    if(now->ls->size+1==num){now->rs=null,now->reset();return mp(now,rs);}    if(num
         
          ls->size){ pr T=split(now->ls,num); now->ls=T.second,now->reset(); return mp(T.first,now); }else{ pr T=split(now->rs,num-now->ls->size-1); now->rs=T.first,now->reset(); return mp(now,T.second); }}il int getrank(int k,int num){ int res=0,ret=10000000; point now=root[k]; while(now!=null){ if(num==now->pos)ret=min(ret,res+now->ls->size+1); if(num<=now->pos)now=now->ls; else res+=now->ls->size+1,now=now->rs; } if(ret==10000000)return res; else return ret;}map
          
           f;int INDEX=0;il vd ins(int num){if(f.find(num)==f.end())f[num]=++INDEX;}int main(){ int a,b,k,n=gi(),m=gi(); null=new node(0),null->size=0; rep(i,1,100000)root[i]=null; rep(i,1,n)scanf("%d",&a),ins(a),Book[i]=f[a],root[Book[i]]=merge(root[Book[i]],new node(i)); char opt; while(m--){ opt=getchar();while(opt!='C'&&opt!='Q')opt=getchar(); if(opt=='Q'){ a=gi(),b=gi(),k=gi(); ins(k),k=f[k]; printf("%d\n",getrank(k,b)-getrank(k,a-1)); }else{ a=gi(),k=Book[a]; pr T,TT; T=split(root[k],getrank(k,a)-1); TT=split(T.second,1); delete TT.first; root[k]=merge(T.first,TT.second); k=gi(),ins(k); k=Book[a]=f[k]; T=split(root[k],getrank(k,a)); root[k]=merge(T.first,merge(new node(a),T.second)); } } rep(i,1,100000)root[i]->del(); delete null; return 0;}

另：一组更(luan)强(zao)的样例

输入样例#2：

10 101 2 1 3 4 3 1 2 1 6Q 2 8 1Q 5 6 3Q 8 9 2C 1 2C 4 2Q 1 10 2C 5 2Q 2 8 2C 5 1Q 1 10 1

输出样例#2：

Output211444

样例解释

1[2 1 3 4 3 1 2]1 6 ans=2

1 2 1 3[4 3]1 2 1 6 ans=1

1 2 1 3 4 3 1[2 1]6 ans=1

2 2 1 2 4 3 1 2 1 6

[2 2 1 2 4 3 1 2 1 6]ans=4

2 2 1 2 2 3 1 2 1 6

2[2 1 2 2 3 1 2]1 6 ans=4

2 2 1 2 1 3 1 2 1 6

[2 2 1 2 1 3 1 2 1 6]ans=4

转载于:https://www.cnblogs.com/xzz_233/p/7396374.html

你可能感兴趣的文章

document

查看>>

定义DoubleArray并将其作为value写入SequenceFile

Struts2学习笔记（十二）类型转换（Type Conversion）（下）

[转]跟紧时代，让你的设计更加popular

Python学习笔记——PyQt控件中文字居中显示

查看>>

JAVA环境下利用solrj二次开发SOlR搜索的环境部署常见错误

查看>>

DexClassLoader和PathClassLoader

查看>>

Beta阶段敏捷冲刺前准备

查看>>