DTOJ2161 Christmas

• 題目
• • 題目描述
  • 輸入格式
  • 輸出格式
  • 樣例
  • • 樣例輸入
    • 樣例輸出
    • 樣例說明
  • 資料範圍與提示
• 題解

題目

題目描述

給出一個長度為 n n n的整數序列。你的程式需要依次完成如下操作：

1. A   a   b   c A~a~b~c A a b c：将區間 [ a , b ] [a,b] [a,b]中的每個數加上 c c c
2. M   a   b   c M~a~b~c M a b c: 對區間 [ a , b ] [a,b] [a,b]中的每個數 x x x，令 x = m a x ( x , c ) x=max(x,c) x=max(x,c)
3. Q   a Q~a Q a：求序列第 a a a個數的值是多少，以及這個值在之前的詢問中改變了多少次，你的程式需要輸出這兩個值

輸入格式

第一行輸入一個數 n n n，表示序列的長度

接下來一行 n n n個數，表示最開始的序列

接下來一行輸入一個數 m m m，表示操作個數

接下來 m m m行，每行一個詢問，其中操作的形式如試題描述（參考樣例）

輸出格式

對于每個詢問輸出兩個數，分别為那個數的值，以及那個數被修改了多少次

樣例

樣例輸入

3
1 2 3
5
A 1 2 4
M 2 3 5
Q 1
Q 2
Q 3
           

樣例輸出

5 1
6 1
5 1
           

樣例說明

第一個操作後序列變成了 5 , 6 , 3 5,6,3 5,6,3

第二次操作後序列變成了 5 , 6 , 5 5,6,5 5,6,5

資料範圍與提示

對于 30 % 30\% 30%的資料， n , m ⩽ 10000 n,m \leqslant 10000 n,m⩽10000

對于另外 30 % 30\% 30%的資料，操作中的值均随機生成的

對于 100 % 100\% 100%的資料， n , m ⩽ 1 0 5 n,m \leqslant 10^5 n,m⩽105

操作過程中所有數字在

int

範圍内

題解

我太菜了，隻會分塊……

這道題使用分塊非常簡單，代碼超短（比如我的代碼就是最短的），記憶體也很小（我的記憶體也是最小的），但是賊慢，跑了 3008 m s 3008ms 3008ms（居然還是第8名）

首先我們規定一些變量： x i x_i xi​表示數值， o p t i opt_i opti​表示操作次數， x a d d i xadd_i xaddi​表示數值的

lazy

标志， o p t a d d i optadd_i optaddi​表示操作次數的

lazy

标志，二維數組 q i , j q_{i,j} qi,j​表示第 i i i塊中，針對 M   a   b   c M~a~b~c M a b c操作的

lazy

标志，保證一維數組 q i q_i qi​中的數值單調遞增， l i l_i li​表示一維數組 q i q_i qi​的長度

對于 A   a   b   c A~a~b~c A a b c操作，如果 a a a和 b b b在同一塊中，那麼就直接下傳标記，直接暴力修改即可

如果 a a a和 b b b不在同一個塊中， a a a和 b b b所在的塊中一樣下傳标記然後暴力修改，中間的直接 x a d d i + = c , o p t a d d i + + xadd_i+=c,optadd_i++ xaddi​+=c,optaddi​++就可以了

對于 M   a   b   c M~a~b~c M a b c操作，如果 a a a和 b b b在同一塊中，那麼就直接下傳标記，直接暴力修改即可

如果 a a a和 b b b不在同一個塊中， a a a和 b b b所在的塊中一樣下傳标記然後暴力修改，對于中間的每一段，如果 c − a d d i > q i , l i c-add_i>q_{i,l_i} c−addi​>qi,li​​（因為如果小于就沒有存儲的必要了），就執行 q i , + + l i = c − a d d i q_{i,++l_i}=c-add_i qi,++li​​=c−addi​

值得一提的是，因為誰也不知道 l i l_i li​等于幾，是以當 l i > 1000 l_i>1000 li​>1000時，我們就下傳一下标記，清空 q i q_i qi​數組

對于 Q   a Q~a Q a，就直接下傳标記然後輸出 x i x_i xi​和 o p t i opt_i opti​即可

但是，整個程式的核心——下傳标記還沒有講呢！

對，下面，我們就來講講這個函數

假設我們需要下傳第 k k k段的内容，那麼，正常操作就是 x i + = x a d d k , o p t i + = o p t a d d k x_i+=xadd_k,opt_i+=optadd_k xi​+=xaddk​,opti​+=optaddk​，但是我們還需要下傳 q i q_i qi​呢！

我們首先找出比 x i x_i xi​大的 q k , j q_{k,j} qk,j​設它的下标為 ( k , t e m p ) (k,temp) (k,temp)（因為數組中的值是單調遞增的，是以直接使用

upper-bound

即可），如果沒有這個 t e m p temp temp，那就直接正常下傳就好了，但是如果有，就說明這個數需要更新成 c c c，并且操作次數要加上 l k − t e m p + 1 l_k-temp+1 lk​−temp+1（因為單調遞增，這個 c − a d d k c-add_k c−addk​更新了，後面的肯定都要更新）

聽起來很難了解，看看代碼實作吧！

附上代碼：

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int n,m,d,x[100010],opt[100010],add[330],Add[330],q[330][1010],l[330];
char op;
void change1(int a,int b,int c)
{
	for(int i=a;i<b;i++) x[i]+=c,opt[i]++;
}
void change2(int a,int b,int c)
{
	for(int i=a;i<b;i++) if(x[i]<c) x[i]=c,opt[i]++;
}
void spread(int k)
{
	for(int i=d*k,temp;i<d*k+d;i++){
    	temp=upper_bound(q[k]+1,q[k]+l[k]+1,x[i])-q[k];
    	if(temp<=l[k]) x[i]=q[k][l[k]],opt[i]+=l[k]-temp+1;
    	opt[i]+=Add[k],x[i]+=add[k];
	}
	l[k]=add[k]=Add[k]=0;
} 
int main()
{
	cin>>n,d=sqrt(n);
	for(int i=0;i<n;i++) cin>>x[i];
	for(int i=0;i<d;i++) q[i][0]=-0x7fffffff;
	cin>>m;
	for(int i=1,a,b,c;i<=m;i++){
    	cin>>op>>a,a--;
    	if(op=='A'){
    		cin>>b>>c,b--;
    		if(!c) continue;
    		if(a/d==b/d){spread(a/d),change1(a,b+1,c);continue;}
			spread(a/d),change1(a,(a/d+1)*d,c);
			for(int i=a/d+1;i<b/d;i++) add[i]+=c,Add[i]++;
			spread(b/d),change1((b/d)*d,b+1,c);
		}
		else if(op=='M'){
			cin>>b>>c,b--;
			if(a/d==b/d){spread(a/d),change2(a,b+1,c);continue;}
			spread(a/d),change2(a,(a/d+1)*d,c);
			for(int i=a/d+1;i<b/d;i++){
	    		if(c-add[i]>q[i][l[i]]) q[i][++l[i]]=c-add[i];
	    		if(l[i]>1000) spread(i);
			}
			spread(b/d),change2((b/d)*d,b+1,c);
		}
		else spread(a/d),cout<<x[a]<<" "<<opt[a]<<endl;
	}
}