P4145 上帝造题的七分钟 2 / 花神游历各国

这道题解法很多，但我主要想提一下势能这个概念。

就像重力势能一样，一个物体只会往下落，且到达零势面之后不会再继续往下落（虽然和真实情况有出入）

因此，我们往往可以利用这个特性，来减少许多不必要的操作；

对于这道题而言，我们发现一个数如果已经开到1，那么再多的操作对他都毫无意义（即到达零势面），此后我们可以忽略掉他。

观察数据范围，每个数最多开六次根，就会变成1，那么我们开一个变量，记录它是否变成1.如果一个区间已全部变成1，那么对于他的修改可直接跳过。

GSS4 - Can you answer these queries IV  （双倍经验）

具体细节见代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+555;
typedef long double lb;
typedef long long ll;
typedef double db;
const ll inf=1e18+10;
const ll mod=1e9+7;
ll a[N];
struct node{
    int l,r;
    ll mx,sum;
}t[N<<2];
void build(int u,int l,int r){
    t[u].l=l;t[u].r=r;
    if(l==r){
        t[u].mx=a[l];
        t[u].sum=a[l];
        return;
    }
    int M=(l+r)>>1;
    build(u<<1,l,M);build(u<<1|1,M+1,r);
    t[u].mx=max(t[u<<1].mx,t[u<<1|1].mx);
    t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
    return;
}
ll ask(int u,int l,int r){
    int L=t[u].l,R=t[u].r;
    if(L>=l&&R<=r){
        return t[u].sum;
    }
    int M=(L+R)>>1;
    ll val = 0;
    if(l <= M) val += ask(u << 1, l, r);
    if(r > M) val += ask(u << 1 | 1, l, r);
    return val;
}
void change(int u,int l,int r){
    int L=t[u].l,R=t[u].r;
    if(t[u].mx<=1) return;
    if(L==R){
        t[u].sum=t[u].mx=sqrt(t[u].mx);
        return;
    }
    int M=(L+R)>>1;
    if(M>=l) change(u<<1,l,r);
    if(M<r) change(u<<1|1,l,r);
    t[u].sum=t[u<<1].sum+t[u<<1|1].sum;
    t[u].mx=max(t[u<<1].mx,t[u<<1|1].mx);
    
}
int n,q;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int q;
    cin>>q;
    build(1,1,n);
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        if(l>r) swap(l,r);
        if(!op) change(1,l,r);
        else cout<<ask(1,l,r)<<endl;
    }
    return 0;
}

我们再思考一道题：

对于一个有正有负的数列，我们有两种操作：

区间加上一个正数；

询问区间绝对值之和。

显然，一个数如果已经被加成正数，那么它永远也无法回到负数的状态。因此我们新增一个变量，记录该区间是否全部变成正数。如果不是的话，我们需要跳到更小区间，对于负数需要单独修改。而一个区间一旦全部为正，就变成了最普通的线段树。

我并不知道这个题应该交到哪

有人知道了告诉我一声

势能线段树虽然考的不多，但势能作为一种很重要的思想，还是有必要掌握的。