【BZOJ-3337】ORZJRY I 块状链表

3337: ORZJRY I

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 190  Solved: 50
[Submit][Status][Discuss]

Description

Jry最近做(屠)了很多数据结构题,所以想 BS你,他希望你能实现一种数据结构维护一个序列:

Input

第一行n;
第二行n个数;
第三行q,代表询问个数;
接下来q行,每行一个op,输入格式见描述。

Output

对于7≤op≤11的操作,一行输出一个答案。

Sample Input

6
5 2 6 3 1 4
15
7 2 4
8 1 3
9 2 4 5
10 1 6 4
11 2 5 4
6 1 4 7
8 1 4
5 3 4 5
2 1
1 2 8
3 3 5
4 1 5 2
9 2 5 4
10 3 6 4
11 1 6 100

Sample Output

11
4
1
4
3
0
3
12
6

HINT

n,q≤100000;
任意时刻数列中的数≤2^31-1。
0≤任意时刻数列中的数≤2^31-1。

本题共3组数据

Source

by orzjry

Solution

switch(opt)
{
  case 1: 直接分裂后插入即可 break;
  case 2: 分裂后直接删除 break;
  case 3: 分裂得到[l,r]将指向l的块指向r,l指向r指向的块,然后给[l,r]中所有块打上反转标记 break;
  case 4: 提取出[r-k,r],将这段从中删除,再整段插入到l之前 break;
  case 5: 提取[l,r],打tag标记 break;
  case 6: 提取[l,r],打del标记 break;
  case 7: 提取[l,r],扫描一遍区间中的所有块,统计sum break;
  case 8: 同上,统计max和min,输出max-min break;
  case 9: 想的还是需要二分,但还没有特别精妙的想法 break;
  case 10: 对每个块额外记录一个排序后的数列,然后找K小 break;
  case 11: 对每个块额外处理一个有序的数列,然后二分统计个数 break;
}

上述这些二分大都可以用STL中的替代,注意的是Split和Merge的时候要PushDown和Update

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
    while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
    return x*f;
}

namespace BlockLists
{
    #define BN
    struct BLNode{int next,from,data[],tmp[],size; int maxx,minn,tag,sum; bool rev;}B[BN];
    queue<int>trash;
    inline int New() {if (trash.empty()) return ++sz; int tmp=trash.front(); trash.pop(); return tmp;}
    inline void Del(int x) {trash.push(x); B[x].next=-1; B[x].size=B[x].maxx=B[x].minn=B[x].sum=B[x].tag=B[x].rev=0;}
    inline int GetP(int rk) {for (int i=start; ~i; i=B[i].next) if (rk>B[i].size) rk-=B[i].size; else return i;}
    inline int GetK(int rk) {for (int i=start; ~i; i=B[i].next) if (rk>B[i].size) rk-=B[i].size; else return rk;}
    inline void Data(int pos,int len,int data[],int suf) {B[pos].next=suf; B[pos].size=len; memcpy(B[pos].data,data,len);}
    inline void PushDown(int x)
    {
        int sz=B[x].size;
        if (B[x].del) {int del=B[x].del; B[x].del=0; for (int i=0; i<sz; i++) B[x].data[i]=del; B[x].sum=sz*del; B[x].maxx=B[x].minn=del;}
        if (B[x].rev) {reverse(B[x].data,B[x].data+sz);}
        if (B[x].tag) {int tag=B[x].tag; B[x].tag=0; for (int i=0; i<sz; i++) B[x].data[i]+=tag; B[x].sum+=sz*tag; B[x].maxx+=tag; B[x].minn+=tag;}
    }
    inline void Update(int x)
    {
        int sz=B[x].size; B[x].sum=0;
        for (int i=0; i<sz; i++) B[x].sum+=B[x].data[i];
        memcpy(B[x].tmp,B[x].data,sz);
        sort(B[x].tmp,B[x].tmp+sz);
    }
    inline void Split(int pos,int rk)
    {
        PushDown(pos);
        if (B[pos]==rk) return;
        int id=New(); Data(id,B[pos].size-rk,B[pos].data+rk,B[pos].next); B[pos].next=id; B[pos].size=rk;
        Update(id); Update(pos);
    }
    inline void Merge(int pos)
    {
        for ( ; ~pos; pos=B[pos].next)
            for (int suf=B[pos].next; ~suf && B[pos].size+B[suf].size<Bsize; suf=B[suf].next)
                PushDown(pos),PushDown(suf),
                memcpy(B[pos].data+B[pos].size,B[suf].data,B[suf].size),B[pos].next=B[suf].next,B[pos].size+=B[suf].size,
                Del(suf),Update(pos);
    }
    inline void Insert(int s)
    {
        int now=GetP(s),pos=GetK(s);  Split(now,pos);
        int id=New(); Data(id,1,a+1,B[now].next); B[now].next=id;
        Merge(now);
    }
    inline void Delete(int s)
    {
        int now=GetP(s),pos=GetK(s); Split(now,pos);
        Del(B[pos].next);
        Merge(now);
    }
    inline void Prework(int l,int r,int &x,int &y)
    {
        int now1=GetP(l),pos1=GetK(l);  Split(now1,pos1);
        int now2=GetP(r),pos2=GetK(r);  Split(now2,pos2);
        x=pos1,y=pos2;
    }
    inline void Rever()
    {

    }
    inline void Change()
    inline void Move()
    inline void Add()
    inline void Modify()
    inline void GetSum()
    inline void GetRange()
    inline void GetClose()
    inline void GetKth()
    inline void GetSmall()
}
using namespace BlockLists;
int main()
{
    int N=read();
    for (int i=1; i<=N; i++) a[0]=read(),Insert(i-1);
    Bsize=ceil(sqrt(N));
    Q=read();
    while (Q--)
        {
            int opt=read(); int x,y,k,val;
            switch (opt)
                {
                    case 1: x=read()-1,val=read(),Change(x,val); break;
                    case 2: x=read()-1; Delete(x); break;
                    case 3: x=read()-1,y=read()-1; Rever(x,y); break;
                    case 4: x=read()-1,y=read()-1,k=read(); Move(x,y); break;
                    case 5: x=read()-1,y=read()-1; val=read(); Add(x,y,val); break;
                    case 6: x=read()-1,y=read()-1; val=read(); Modify(x,y,val); break;
                    case 7: x=read()-1,y=read()-1; GetSum(x,y); break;
                    case 8: x=read()-1,y=read()-1; GetRange(x,y); break;
                    case 9: x=read()-1,y=read()-1; GetClose(x,y); break;
                    case 10: x=read()-1,y=read()-1,k=read(); GetKth(x,y,k); break;
                    case 11: x=read()-1,y=read()-1,val=read(); GetSmall(x,y,val); break;
                }
        }
    return 0;
}

还没实现完

时间: 09-15

【BZOJ-3337】ORZJRY I 块状链表的相关文章

【BZOJ2741】【块状链表+可持久化trie】FOTILE模拟赛L

Description FOTILE得到了一个长为N的序列A,为了拯救地球,他希望知道某些区间内的最大的连续XOR和. 即对于一个询问,你需要求出max(Ai xor Ai+1 xor Ai+2 ... xor Aj),其中l<=i<=j<=r. 为了体现在线操作,对于一个询问(x,y): l = min ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).r = max ( ((x+lastans) mod N)+1 , ((y+last

【POJ2887】【块状链表】Big String

Description You are given a string and supposed to do some string manipulations. Input The first line of the input contains the initial string. You can assume that it is non-empty and its length does not exceed 1,000,000. The second line contains the

c++之路进阶——块状链表(弹飞绵羊)

2333 弹飞绵羊 2010年省队选拔赛湖南 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 大师 Master 题解 题目描述 Description Lostmonkey发明了一种超级反弹装置.为了在绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏.游戏一开始,Lostmonkey在地上沿一条直线摆放 n个反弹装置,并按从前往后的方式将反弹装置依次编号为 0 到 n-1,对 0≤i≤n-1,为第 i 个反弹装置设定了初始弹力系数 ki,当绵羊落到第 i 个反弹装置上时,它将被往后

c++之路——块状链表(教主的魔法)

F.A.Qs Home Discuss ProblemSet Status Ranklist Contest ModifyUser  gryz2016 Logout 捐赠本站 Notice:由于本OJ建立在Linux平台下,而许多题的数据在Windows下制作,请注意输入.输出语句及数据类型及范围,避免无谓的RE出现. 3343: 教主的魔法 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 711  Solved: 309[Submit][Stat

hdu 1754 块状链表 单点修改+单点查询

经典的线段树题目,也可以用块状链表做. 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 using namespace std; 6 7 const int N = 200000; 8 const int M = 800; 9 int n, m, tot; 10 11 int max( int a, int b ) 12 { 13 retu

poj 2887 块状链表

块状链表第一题,懒得写成链表形式的,所以写成了静态链表. 思想还是很简单的,就是进行分块查找和插入,和建立索引有点像,复杂度是根号的,实现起来比较容易,由于这个题插入操作不多,所以没有写split函数, 因为没有删除操作,所以也没有写union函数,随后有空再补上吧. 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 using namesp

【BZOJ1500】【块状链表】SuperMemo

Description Input 输入文件的第1行包含两个数N和M,N表示初始时数列中数的个数,M表示要进行的操作数目.第2行包含N个数字,描述初始时的数列.以下M行,每行一条命令,格式参见问题描述中的表格. Output 对于输入数据中的GET-SUM和MAX-SUM操作,向输出文件依次打印结果,每个答案(数字)占一行. Sample Input 9 8 2 -6 3 5 1 -5 -3 6 3 GET-SUM 5 4 MAX-SUM INSERT 8 3 -5 7 2 DELETE 12

bzoj 1588 [HNOI2002] 营业额统计 链表和Splay

来自HNOI 2002营业额的统计一题,这题以前是用链表水过的,最近看见许多splay的题,赶紧张一下知识. 题目大意就是对于一个序列,输出每个元素与它之前元素的差的最小值的和.先说链表的方法吧. 大概就是sort一下,记录每个点的rank.然后链表一下,很好理解,复杂度nlogn,瓶颈在于排序. #include<cstdio> #include<algorithm> #include<iostream> using namespace std; struct nod

通用块状链表

在这里写下模板.以后方便用 #include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #define max_size 3000 using namespace std; const int best_size = max_size - 20; struct node { int size; int date[m

BZOJ 1098 [POI2007]办公楼biu 链表

description Bytel is a mobile telephony potentate. Each employee has been issued a company phone, the memory ofwhich holds the numbers of some of his co-workers (all of them have his number in their phones as well). Due to dynamic growth of their ope