CSES 1736-Polynomial Queries 解題心得( 題目 )
解題概念:線段樹、懶標記(lazy propagation)
解題方法:先建造一個線段數st，另外這題需要支援區間修改，所以必須使用懶標記(lazy propagation)，不然複雜度會爆掉，而懶標需要記住甚麼呢? 如果我們要算一個等差數列的sum(用公式)，需要首項a、以及公差d(其實還有項數)，所以，在下面的程式碼中需要兩個懶標(a、d分別記做lta、ltd)。
懶標的計算與下移:首先查詢時到達了有懶標的節點，我們可以根據sum=n*(2a1+(n-1)d)/2的公式，其中n就是該節點管轄的範圍l,r的差(記得+1)，把這個直加到目前的節點上，轉成程式就是就是st[c]+=(r-l+1)*(2*lta[c]+(r-l)*ltd[c])/2，再來下移的方式是把左右子節點加上父節點的d，而a的部分是左邊加上a，右邊加上a+d*((l+r)/2-l+1) (原本首項加上左界到中間乘上公差)，下面說明為什麼這樣做!)
數學觀察:1+2+3 可視為3*(2*1+1(3-1))/2，而3+5+7可視為3*(2*3+2(3-1))/2，相加可變成 (1+3)+(2+5)+(3+7) ，也就是一個首項為1+3，公差為1+2的等差級數，所以我們可以分別透過首項、公差相加的方式來進行懶標的計算。
註:readnum()函式式讀取測資用，另外這篇文章只要能理解原理其實就會解這題了，我自己認為下面的程式有點亂，所以程式碼僅供參考用。
Java參考程式碼(有更好意見可留言於下方，謝謝!)
import java.io.*;
public class cses1736 {
public static long[] st,lta,ltd,num;
public static int ret,r;
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception{
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
final int n=readnum();
final int q=readnum();
num=new long[n+5];
st=new long[4*n];
lta=new long[4*n];
ltd=new long[4*n];
for(int i=1;i<=n;i++) {
num[i]=readnum();
}
build(1,n,1);
int f;
for(int i=0;i<q;i++) {
f=readnum();
if(f==2) {
bw.write(query(1,n,1,readnum(),readnum())+"\n");
}
else {
update(1,n,1,readnum(),readnum());
}
}
bw.flush();
}
public static long build(int l,int r,int c) {
if(l==r) {
st[c]=num[l];
}
else {
int mid=(l+r)/2;
st[c]=build(l,mid,c*2)+build(mid+1,r,c*2+1);
}
return st[c];
}
public static long query(long l,long r,int c,int ql,int qr) {
if(l>qr||r<ql) {
return 0;
}
if(ltd[c]!=0) {
if(l!=r) {
ltd[2*c]+=ltd[c];
ltd[2*c+1]+=ltd[c];
lta[2*c]+=lta[c];
lta[2*c+1]+=(lta[c]+ltd[c]*((l+r)/2-l+1));
}
st[c]+=(r-l+1)*(2*lta[c]+(r-l)*ltd[c])/2;
ltd[c]=lta[c]=0;
}
if(l<ql||r>qr) {
long mid=(l+r)/2;
return query(l,mid,c*2,ql,qr)+query(mid+1,r,c*2+1,ql,qr);
}
return st[c];
}
public static long update(long l,long r,int c,int tl,int tr){
if(l>tr||r<tl) {
return 0;
}
if(l<tl||r>tr) {
long mid=(l+r)/2;
long re=update(l,mid,c*2,tl,tr)+update(mid+1,r,c*2+1,tl,tr);
st[c]+=re;
return re;
}
else{
lta[c]+=l-tl+1;
ltd[c]+=1;
return (r-l+1)*(2*(l-tl+1)+(r-l))/2;
}
}
public static int readnum() throws Exception {
ret=0;
r=br.read();
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
return ret;
}
}
文章標籤
全站熱搜
