傳送門
很明顯可以用線段樹!(簡直是模闆題)
線段樹:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define g getchar()
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct node{int l,r;ll c,ad;}tr[N<<2];
int n,m;
ll a[N];
void bt(int p,int l,int r)
{
tr[p].l=l;tr[p].r=r;
if(tr[p].l==tr[p].r){tr[p].c=a[l];return;}
int mid=(l+r)>>1;
bt(lc,l,mid);bt(rc,mid+1,r);
tr[p].c=tr[lc].c+tr[rc].c;
}
void wh(int p)
{
tr[lc].ad+=tr[p].ad;tr[rc].ad+=tr[p].ad;
tr[lc].c+=tr[p].ad*(tr[lc].r-tr[lc].l+1);
tr[rc].c+=tr[p].ad*(tr[rc].r-tr[rc].l+1);
tr[p].ad=0;
}
void add(int p,int l,int r,ll k)
{
if(l<=tr[p].l&&tr[p].r<=r)
{tr[p].ad+=k;tr[p].c+=k*(tr[p].r-tr[p].l+1);return;}
if(tr[p].ad)wh(p);
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid)add(lc,l,r,k);
if(mid<r)add(rc,l,r,k);
tr[p].c=tr[lc].c+tr[rc].c;
}
ll ans;
void ask(int p,int l,int r)
{
if(l<=tr[p].l&&tr[p].r<=r){ans+=tr[p].c;return;}
if(tr[p].ad)wh(p);
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid)ask(lc,l,r);
if(mid<r)ask(rc,l,r);
}
template<class o>
void qr(o&x)
{
char c=g;bool v=(x=0);
while(!( ('0'<=c&&c<='9') || c=='-' ))c=g;
if(c=='-')v=1,c=g;
while('0'<=c&&c<='9')x=x*10+c-'0',c=g;
if(v)x=-x;
}
void write(ll x)
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
void pri(ll x)
{
if(x<0)putchar('-'),x=-x;
write(x);puts("");
}
int main()
{
qr(n);qr(m);
for(int i=1;i<=n;i++)qr(a[i]);
bt(1,1,n);
while(m--)
{
char s[2];int l,r;ll d;
scanf("%s",s);qr(l);qr(r);
switch(s[0]){
case 'C':
qr(d);
add(1,l,r,d);
break;
case 'Q':
ans=0;
ask(1,l,r);
pri(ans);
break;
}
}
return 0;
}
樹狀數組:
樹狀數組是隻能維護字首和的,但是這題一點樹狀數組的痕迹都沒有.QwQ
對于區間加,我們很容易聯想到差分。那我們試試吧。
設 a [ i ] , c [ i ] 分 别 表 示 原 數 列 的 第 i 個 位 置 的 值 , 第 i 個 位 置 的 變 化 量 ( 可 以 為 負 ) , b [ i ] = c [ i ] − c [ i − 1 ] — — b 為 c 的 差 分 數 組 , s u m 為 a 的 前 綴 和 設a[i],c[i]分别表示原數列的第i個位置的值,第i個位置的變化量(可以為負),b[i]=c[i]-c[i-1]——b為c的差分數組,sum為a的字首和 設a[i],c[i]分别表示原數列的第i個位置的值,第i個位置的變化量(可以為負),b[i]=c[i]−c[i−1]——b為c的差分數組,sum為a的字首和
那麼 ∑ i = 1 x b [ i ] = c [ x ] \sum_{i=1}^x b[i]=c[x] ∑i=1xb[i]=c[x],于是 a [ x ] + ∑ i = 1 x b [ i ] = a [ x ] + c [ x ] ( 第 i 個 位 置 的 當 前 值 ) a[x]+\sum_{i=1}^x b[i]=a[x]+c[x](第i個位置的目前值) a[x]+∑i=1xb[i]=a[x]+c[x](第i個位置的目前值)
那麼前x項的和可表示為:
s u m [ x ] + ∑ i = 1 x ∑ j = 1 i b [ j ] = s u m [ x ] + ∑ i = 1 x ( x − i + 1 ) ∗ b [ i ] = sum[x]+\sum_{i=1}^x \sum_{j=1}^i b[j]=sum[x]+\sum_{i=1}^x(x-i+1)*b[i]= sum[x]+∑i=1x∑j=1ib[j]=sum[x]+∑i=1x(x−i+1)∗b[i]=
s u m [ x ] + ∑ i = 1 x ( x + 1 ) b [ i ] − ∑ i = 1 x i ∗ b [ i ] sum[x]+\sum_{i=1}^x (x+1)b[i]-\sum_{i=1}^x i*b[i] sum[x]+∑i=1x(x+1)b[i]−∑i=1xi∗b[i] ( 這 樣 前 綴 和 ( 兩 個 Σ 内 的 ) 就 不 方 便 用 樹 狀 數 組 維 護 ， 因 為 前 綴 和 中 有 與 i 無 關 的 項 ( x + 1 ) ， 所 以 我 們 需 要 把 x + 1 提 出 來 ） (這樣字首和(兩個\Sigma内的)就不友善用樹狀數組維護，因為字首和中有與i無關的項(x+1)，是以我們需要把x+1提出來） (這樣字首和(兩個Σ内的)就不友善用樹狀數組維護，因為字首和中有與i無關的項(x+1)，是以我們需要把x+1提出來）
s u m [ x ] + ( x + 1 ) ∑ i = 1 x b [ i ] − ∑ i = 1 x i ∗ b [ i ] sum[x]+(x+1)\sum_{i=1}^x b[i]-\sum_{i=1}^x i*b[i] sum[x]+(x+1)∑i=1xb[i]−∑i=1xi∗b[i]
那麼我們用一個數組維護 b [ i ] b[i] b[i]的字首和,一個數組維護 b [ i ] ∗ i b[i]*i b[i]∗i的字首和就行.
(代碼中具體為 c 1 , c 2 c1,c2 c1,c2)
不禁感歎這種思路的巧妙
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define gc getchar()
#define ll long long
#define TP template<class o>
using namespace std;
const int N=1e5+10;
TP void qr(o&x) {
char c=gc; x=0; int f=1;
while(!isdigit(c)){if(c=='-') f=-1; c=gc;}
while(isdigit(c))x=x*10+c-'0',c=gc;
x*=f;
}
TP void qw(o x) {
if(x<0) putchar('-'),x=-x;
if(x/10) qw(x/10);
putchar(x%10+'0');
}
TP void pr2(o x) {qw(x); puts("");}
int n,m;
ll a[N],c1[N],c2[N];
void add(int x,ll y) {
for(ll z=x*y;x<=n;x+=x&-x)
c1[x]+=y,c2[x]+=z;
}
void add(int l,int r,ll d) {add(l,d); add(r+1,-d);}
ll ask(int x) {
ll s=0;
for(ll y=x+1;x;x&=x-1) s+=y*c1[x]-c2[x];
return s;
}
ll ask(int l,int r) {return ask(r)-ask(l-1)+a[r]-a[l-1];}
int main() {
qr(n); qr(m);
for(int i=1;i<=n;i++) qr(a[i]),a[i]+=a[i-1];
while(m--) {
char s[5];int l,r,d;
scanf("%s",s); qr(l); qr(r);
if(s[0]=='C') qr(d),add(l,r,d);
else pr2(ask(l,r));
}
return 0;
}
分塊
之前我們學 B S G S ( A x ≡ B ( m o d C ) ) BSGS(A^x≡B(mod~~C)) BSGS(Ax≡B(mod C))就用到了分塊的思想.
以後我們學莫比烏斯反演的時候,會用到整除分塊——一種十分巧妙的方法。
現在我們來做算法進階給出的分塊模闆題。
分塊是一種用空間換取時間，達到時空平衡的“樸素算法”。效率往往比不上樹狀數組與線段樹，但是它更加通用，容易實作。大部分常見的分塊思想都可以用“大段維護，局部樸素”來形容
我們把數列A分成若幹塊長度不大于 s q r t ( n ) sqrt(n) sqrt(n)的塊,其中第i塊的左端點為 ( i − 1 ) ∗ s q r t ( n ) (i-1)*sqrt(n) (i−1)∗sqrt(n),右端點為 i ∗ s q r t ( n ) i*sqrt(n) i∗sqrt(n).
對于大段操作,我們直接給段打上标記.至于小段,直接暴力.
代碼:
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define g getchar()
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int T=333;//段數
ll a[N],sum[T],add[T];
int L[T],R[T],n,m,t,pos[N];
void change(int l,int r,ll d)//大段維護,小段樸素
{
int p=pos[l],q=pos[r];
if(p==q)
{
for(int i=l;i<=r;i++)a[i]+=d;
sum[p]+=d*(r-l+1);
}
else
{
for(int i=p+1;i<=q-1;i++)add[i]+=d;
for(int i=l;i<=R[p];i++)a[i]+=d;
sum[p]+=d*(R[p]-l+1);
for(int i=L[q];i<=r;i++)a[i]+=d;
sum[q]+=d*(r-L[q]+1);
}
}
ll ask(int l,int r)
{
int p=pos[l],q=pos[r];
ll ans=0;
if(p==q)
{
for(int i=l;i<=r;i++)ans+=a[i];
ans+=add[p]*(r-l+1);
}
else
{
for(int i=p+1;i<=q-1;i++)
ans+=sum[i]+add[i]*(R[i]-L[i]+1);
for(int i=l;i<=R[p];i++)ans+=a[i];
ans+=add[p]*(R[p]-l+1);
for(int i=L[q];i<=r;i++)ans+=a[i];
ans+=add[q]*(r-L[q]+1);
}
return ans;
}
template<class o>
void qr(o&x)
{
char c=g;bool v=(x=0);
while(!( ('0'<=c&&c<='9') || c=='-' ))c=g;
if(c=='-')v=1,c=g;
while('0'<=c&&c<='9')x=x*10+c-'0',c=g;
if(v)x=-x;
}
void write(ll x)
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
void pri(ll x)
{
if(x<0)putchar('-'),x=-x;
write(x);puts("");
}
int main()
{
qr(n);qr(m);
for(int i=1;i<=n;i++)qr(a[i]);
//分塊
t=sqrt(n*1.0);
for(int i=1;i<=t;i++)
{
L[i]=R[i-1]+1;
R[i]=i*t;
}
if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
//預處理
for(int i=1;i<=t;i++)
for(int j=L[i];j<=R[i];j++)
pos[j]=i,sum[i]+=a[j];
//指令
while(m--)
{
char s[2];scanf("%s",s);
int l,r;ll d;qr(l);qr(r);
switch(s[0]){
case 'C':
qr(d);change(l,r,d);
break;
case 'Q':
pri(ask(l,r));
}
}
return 0;
}
![CF1446F - Line Distance[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)