ZJ c652: 四、帶修改區間和(MRSQ) 線段樹開根號

線段樹開根號,因開根號相加後不等於相加開根號
所以不能用lazy tag傳值快速更新
只能找到區間的葉節點開根號後push up
這裡可以做一個優化
因為開根號很快就會變成1
所以可以設一個tag往上傳遞
當葉節點的值為1時
將tag設為true
如果修改到tag值為true的點時
就不要理他
以下為code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define AC ios::sync_with_stdio(0),cin.tie(0);

struct node
{
int l,r;
ll sum;
bool lazy;
void update()
{
sum=sqrt(sum);
}
} st[300000*4+1];

void push_up(int x)
{
st[x].sum=st[x<<1].sum+st[x<<1|1].sum;
st[x].lazy=st[x<<1].lazy&st[x<<1|1].lazy;
}

void build(int x,int l,int r)
{
st[x].l=l,st[x].r=r,st[x].sum=0,st[x].lazy=0;
if(l==r)
{
cin>>st[x].sum;
if(st[x].sum==1) st[x].lazy=1;
}
else
{
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
push_up(x);
}
}

void modify(int x,int l,int r)
{
if(st[x].lazy==1) return;
int L=st[x].l,R=st[x].r;
if(L==R)
{
st[x].update();
if(st[x].sum==1) st[x].lazy=1;
}
else
{
int mid=(L+R)>>1;
if(l<=mid) modify(x<<1,l,r);
if(r>mid) modify(x<<1|1,l,r);
push_up(x);
}
}

ll query(int x,int l,int r)
{
int L=st[x].l,R=st[x].r;
if(L>=l&&R<=r) return st[x].sum;
else
{
int mid=(L+R)>>1;
ll ans=0;
if(l<=mid) ans+=query(x<<1,l,r);
if(r>mid) ans+=query(x<<1|1,l,r);
push_up(x);
return ans;
}
}

int main()
{
AC
int n,q;
cin>>n>>q;
build(1,1,n);
while(q--)
{
int t,l,r;
cin>>t>>l>>r;
if(t) modify(1,l,r);
else cout<<query(1,l,r)<<'\n';
}
}

留言

張貼留言

這個網誌中的熱門文章

TIOJ 1080 . A.逆序數對 (BIT解法)

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1080 先做一波離散化 把所需的BIT長度壓到10⁵以內 而後就記錄目前放了幾個數字進BIT 用放了幾個數字減去有幾個數字比當前輸入的數字小(BIT存的) 就是當前的逆序數對 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std; using namespace __gnu_cxx; using namespace __gnu_pbds; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); #define lowbit ( x ) x &- x ll n; struct BIT { vector < ll > v; void modify ( ll x , ll val ) { for (;x < v. size ();x += lowbit (x)) v[x] += val; } ll query ( ll x ) { ll t = 0 ; for (;x;x -= lowbit (x)) t += v[x]; return t; } }; int main () { AC ll num = 1 ; while (cin >> n && n) { cout << " Case # " << num ++<< " : " ; ll cnt = 0 ,r = 0 ,rnk = 1 ; BIT sum; vector < ll > v (n); set < ll > s; ...
閱讀完整內容

ZJ d718: Waiting In Line

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d718 這題是模擬排隊 不過有一個插隊的情況 於是我們用list取代queue 我們用一個unordered_map去存這些人分別屬於哪些團體 方便之後查詢 再來我們用一個vector去存這些團體是否在list中 在的話就進行插隊 而插隊我們用一個vector去存現在這個隊伍中每個團體的最後一個人所在的iterator 就解決啦 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std ; using namespace __gnu_cxx ; using namespace __gnu_pbds ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,m,t,cnt = 1 ; while (cin >> n) { cout << " Line # " << cnt ++<< ' \n ' ; unordered_map <int , int> um; for ( int i = 0 ;i < n;i ++ ) { cin >> m; for ( int j = 0 ;j < m;j ++ ) { cin >> t; um[t] = i; } } string s; list <int> l; vector <int> v (n + 1 , 0 ); vector ...
閱讀完整內容

AtCoder Educational DP Contest E - Knapsack 2

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_e 這題還蠻有趣的 他的重量開到10⁹導致不能用上一題(常規0/1背包)的做法去做 要把價值當做dp轉移,去找當前價值所需的最小重量 最後找到的最大的小於重量限制的價值就是答案 以下為code #include < bits/stdc++.h > using namespace std ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,w,r = 0 ; cin >> n >> w; vector < ll > dp ( 100001 , 1 e 10 ); dp[ 0 ] = 0 ; for ( int i = 0 ;i < n;i ++ ) { int wei,val; cin >> wei >> val; for ( int j = 100000 ;j >= val;j -- ) dp[j] = min (dp[j],dp[j - val] + wei); } for ( int i = 1 ;i < dp. size ();i ++ ) if (dp[i] <= w) r = i; cout << r << ' \n ' ; }
閱讀完整內容