「BZOJ3678」wangxz与OJ
Description
某天，wangxz神犇来到了一个信息学在线评测系统(Online Judge)。由于他是一位哲♂学的神犇，所以他不打算做题。他发现这些题
目呈线性排列，被标记为1~n号，每道题都有一个难度值(可以<=0)。他决定与这些题目玩♂耍。
1、他可以在某个位置插♂入一些难度值特定的题目。
2、他可以吃♂掉(删除)一段题目。
3、他可以查询某个位置的题目的难度值。
维护一个初始有n个元素的序列(标记为1~n号元素)，支持以下操作：
0 p a b (0<=p<=当前序列元素个数) (a<=b) 在p位置和p+1位置之间插入整数:a,a+1,a+2,…,b-1,b。若p为0，插在序列最前面;
1 a b (1<=a<=b<=当前序列元素个数) 删除a,a+1,a+2,…,b-1,b位置的元素;
2 p (1<=p<=当前序列元素个数) 查询p位置的元素。
Input
输入第一行包括两个正整数n(1<=n<=20000),m(1<=m<=20000),代表初始序列元素个数和操作个数。
接下来n个整数,为初始序列元素。
接下来m行,每行第一个为整数sym,
若sym=0,接下来有一个非负整数p,两个整数a,b;
若sym=1,接下来有两个正整数a,b;
若sym=2,接下来有一个正整数p;
p、x、y的含义及范围见题目描述。
在任何情况下，保证序列中的元素总数不超过100000。
保证题目涉及的所有数在int内。
Output
对每个sym=2，输出一行，包括一个整数，代表询问位置的元素。
Sample Input
5 3
1 2 3 4 5
0 2 1 4
1 3 8
2 2
1 2 3 4 5
0 2 1 4
1 3 8
2 2
Sample Output
2
题解
为何此题rope要用short T T
过了几天，发现改了数据。。。于是rope被卡了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<iostream> #include<cstdio> #include<cstring> #include<ext/rope> using namespace std; using namespace __gnu_cxx; inline 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; } int n,m; short t[100005]; rope <short> q; int main() { n=read();m=read(); for(int i=0;i<n;i++) t[i]=read(); q=rope<short>(t,t+n); int a,b,p; for(int i=1;i<=m;i++) { int f=read(); switch(f) { case 0: { p=read();a=read();b=read(); for(int i=a;i<=b;i++) t[i-a]=i; q=q.substr(0,p)+rope<short>(t,t+b-a+1)+q.substr(p,q.size()-p); break; } case 1: { a=read();b=read();a--; q.erase(a,b-a); break; } case 2:p=read();printf("%d\n",q[p-1]);break; } } return 0; } |
计数器 9793122
OI 课件=>
OI 课件=>
貌似这种做法的最坏复杂度是100000*m的吧？
但是我想不到靠谱做法
splay维护,每次只加一个点，要动的时候在分裂