題目鏈接：點擊查看

題目大意：給出一個數(shù)列 a 和一個數(shù)列 b ，其中數(shù)列 a 初始時全部為 0 ，數(shù)列 b 初始時是一個 1 ~ n 的排列，接下來共有 m 次操作，每次操作分為兩種：

add l r ：在區(qū)間 [ l , r ] 內(nèi)的 a[ i ] 都加上 1

query l r ：查詢區(qū)間 [ l , r ] 內(nèi)的所有 ?之和

題目分析：如果直接維護 a[ i ] / b[ i ] 的話可能不太好維護，但是我們可以反向思考，對于數(shù)列 b 維護一個線段樹，每個節(jié)點維護一個 mmin 和一個 sum，分別代表區(qū)間內(nèi)的最小值以及當(dāng)前區(qū)間的貢獻，這個最小值代表的是：當(dāng)前區(qū)間至少還需要進行多少次 add 操作才會產(chǎn)生貢獻，因為初始時每個葉子結(jié)點的 mmin 都將其賦值為 b[ i ] ，這樣每次執(zhí)行 add 操作時，如果 mmin > 1 的話，那么直接讓 mmin 減一即可，如果 mmin = 1 的話，說明當(dāng)前區(qū)間中，存在葉子結(jié)點經(jīng)過此次 add 后悔變成 0 ，也就是 a[ i ] / b[ i ] 可以多貢獻 1 了，對于所有 mmin = 1 的區(qū)間，繼續(xù)向下遞歸，直到葉子結(jié)點位置，此時將葉子結(jié)點的 mmin 重新賦值為 b[ i ] ，并且將 sum 加一就好了

因為是區(qū)間修改和區(qū)間查詢，所以需要加一個 lazy 標(biāo)記

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int l,r,mmin,sum,lazy; }tree[N<<2];int a[N];void pushup(int k) {tree[k].mmin=min(tree[k<<1].mmin,tree[k<<1|1].mmin);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }void pushdown(int k) {if(tree[k].lazy){int lz=tree[k].lazy;tree[k].lazy=0;tree[k<<1].lazy+=lz;tree[k<<1].mmin+=lz;tree[k<<1|1].lazy+=lz;tree[k<<1|1].mmin+=lz;} }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].sum=tree[k].lazy=0;if(l==r){tree[k].mmin=a[l];return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return;if(tree[k].l>=l&&tree[k].r<=r){if(tree[k].mmin>1){tree[k].mmin--;tree[k].lazy--;return;}else if(tree[k].l==tree[k].r){tree[k].mmin=a[tree[k].l];tree[k].sum++;return;}}pushdown(k);update(k<<1,l,r);update(k<<1|1,l,r);pushup(k); }int query(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].sum;pushdown(k);return query(k<<1,l,r)+query(k<<1|1,l,r); }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)scanf("%d",a+i);build(1,1,n);while(m--){char s[10];int l,r;scanf("%s%d%d",s,&l,&r);if(s[0]=='a')update(1,l,r);elseprintf("%d\n",query(1,l,r));}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 6315 Naive Operations(线段树+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。