loj#6282. 数列分块入门 6

#6282. 数列分块入门 6

题目：传送门

简要题意：

　　给出一个长为

题解：

　　不得不说hzwer有点懒

　　好好打分块：

　　分块的题实在是越来越恶心，越来越暴力了....

　　第一反应就是硬插...然后重新分块...感觉要爆...%一发hzwer

　　结果...每次其实最多就影响两个块...爆？不存在的...

　　然后就是一通乱搞...加够了那么多个数再重新分块...

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int n,p,T,a[1100][2100],b[1100][2100];
 8 int block,len[2100];
 9 void reset()
10 {
11     int y=0,k=p/block,ll=0;
12     if(p%block!=0)k++;
13     p+=block;block=sqrt(p);T=0;
14     for(int i=1;i<=k;i++)
15         for(int j=1;j<=len[i];j++)
16         {
17             y++;
18             int kk=(y-1)/block+1;
19             b[kk][++ll]=a[i][j];
20             a[i][j]=0;
21             if(ll==block)ll=0;
22         }
23     k=p/block;if(p%block!=0)k++;
24     for(int i=1;i<=k;i++)
25     {
26         if(i!=k || p%block==0)len[i]=block;
27         else len[i]=p-block*block;
28         for(int j=1;j<=len[i];j++)a[i][j]=b[i][j];
29     }
30 }
31 int main()
32 {
33     scanf("%d",&n);p=n;block=sqrt(n);
34     for(int i=1;i<=n;i++)
35     {
36         int kk=(i-1)/block+1;
37         int x;scanf("%d",&x);
38         a[kk][++len[kk]]=x;
39     }
40     T=0;
41     for(int i=1;i<=n;i++)
42     {
43         int opt,l,r,c;scanf("%d%d%d%d",&opt,&l,&r,&c);
44         if(opt==0)
45         {
46             int k=0,t;
47             for(t=1;t<=block;t++)
48             {
49                 if(k+len[t]>=l)break;
50                 k+=len[t];
51             }
52             len[t]++;
53             for(int j=len[t];j>=l-k+1;j--)a[t][j]=a[t][j-1];a[t][l-k]=r;
54             T++;if(T==block)reset();
55         }
56         else
57         {
58             int k=0,t;
59             for(t=1;t<=block;t++)
60             {
61                 if(k+len[t]>=r)break;
62                 k+=len[t];
63             }
64             printf("%d
",a[t][r-k]);
65         }
66     }
67     return 0;
68 }