HDU-4037 Can you answer these queries?(线段树)

xiaoxiao2021-03-01  15

Can you answer these queries?

题目链接: H - Can you answer these queries? HDU - 4027

题意

给你N个数A[i],给你M个操作,每次操作一个区间 [l,r] [ l , r ] ,有两种操作。

将区间内的数都变成自己的根号,取整求区间 [l,r] [ l , r ] 的和

数据范围: N,M<105 N , M < 10 5


思路

这题直接看的话非常会觉得非常复杂,因为这里的操作无法区间一起进行,每个数进行开根号都只能单个进行。但是有个规律,就在long long int 的范围里面数字最多只会开到7次,所以根据这个性质,我们就可以优化了。

优化方案一

记录每个点修改的次数,利用add延迟标记,在查询的时候修改。更新复杂度 O(logn) O ( l o g n ) ,查询复杂度 O(nlogn) O ( n l o g n ) ,但是在修改时记录每个点所修改的次数,如果次数大于7就修改为7,这样的复杂度其实毫无疑问就会T的。

优化方案二

方案一会T的原因就是如果有多次查询那么我们就会复杂度非常高。我们从另一个角度来考虑,就更新复杂度 O(nlogn) O ( n l o g n ) 查询复杂度 O(logn) O ( l o g n ) 虽然表面上看是一样的,但是因为每个点所修改最多只用7次,所以最多修改7*N次,最多修改所需要 7O(logn) 7 ∗ O ( l o g n ) ,这里非常有意思,我看大神的代码学会一种线段树的新型写法,就是分层写线段树,这里给出的代码二就这样,一般的线段树所用的是只用一个递归函数,而我这里需要两种递归,就是在一开始时有一个查找区间 [L,R] [ L , R ] 的Update,然后找到这个区间后使用Update2,将这个区间里面的值都修改为根号,并且将这个区间(包括所有的子区间)的标记add加上一。

优化方案三

这是一种属于这道题的专门的优化方案,就是如果一段区间无法在修改时,每个值一定都是一所以,在修改时,如果发现这个区间的sum是等于r-l+1的,那么就直接return这个区间的值即可。


代码

优化方案二

#include <bits/stdc++.h> using namespace std; #define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++) #define per(i,j,k) for(int i = (int)j;i >= (int)k;i --) #define mmm(a,b) memset(a,b,sizeof(a)) #define debug(x) cerr<<#x<<":"<<x<<endl #define pb push_back typedef double db; typedef long long ll; const int MAXN = (int)1e5+7; const int INF = (int)0x3f3f3f3f; #define rson rt<<1|1 #define lson rt<<1 ll A[MAXN]; int N,M; struct SetTree{ ll sum; int add; }tree[MAXN<<2]; void Build(int l,int r,int rt){ if (l == r){ tree[rt].sum = A[l]; tree[rt].add = 0; return; } int m = l+r>>1; Build(l,m,lson); Build(m+1,r,rson); tree[rt].sum = tree[lson].sum + tree[rson].sum; } void PushDown(int rt){ if (tree[rt].add){ tree[lson].add = tree[rson].add = tree[rt].add; } } void Updates(int l,int r,int rt){ tree[rt].add ++; if (l == r) { tree[rt].sum = (ll)sqrt(tree[rt].sum); return; } int m = l+r>>1; Updates(l,m,lson); Updates(m+1,r,rson); tree[rt].sum = tree[lson].sum + tree[rson].sum; } void Update(int L,int R,int l,int r,int rt){ if (L <= l && r <= R) { if (tree[rt].add <= 7) Updates(l,r,rt);//tree[rt].add ++; return; } int m = l+r>>1; if (L <= m) Update(L,R,l,m,lson); if (R > m) Update(L,R,m+1,r,rson); tree[rt].sum = tree[lson].sum + tree[rson].sum; } ll Query(int L,int R,int l,int r,int rt){ if (L <= l && r <= R){ return tree[rt].sum; } int m = l+r>>1; ll res = 0; if (L <= m)res += Query(L,R,l,m,lson); if (R > m)res += Query(L,R,m+1,r,rson); return res; } int main() { int ca = 0; while (~scanf("%d",&N)){ printf("Case #%d:\n",++ca); rep(i,1,N) scanf("%lld",&A[i]); mmm(tree,0); Build(1,N,1); scanf("%d",&M); rep(i,1,M) { int op,l,r; scanf("%d %d %d",&op,&l,&r); if (l > r) swap(l,r); if (op){ printf("%lld\n",Query(l,r,1,N,1)); }else { Update(l,r,1,N,1); } } printf("\n"); } }
转载请注明原文地址: https://www.6miu.com/read-4050062.html

最新回复(0)