D - Counting Stars HDU - 7059

題解:

長度為n的序列a，有三個操作：

對某個區(qū)間進(jìn)行詢問

對于某個區(qū)間內(nèi)的每個數(shù)ai，減去ai&(-ai)

對于某個區(qū)間內(nèi)的每個數(shù)ai，加上$2^k$,k滿足$2^k<=a_i<2^{k+1}$

題解：

很容易想到線段樹維護(hù)，但是后兩個操作都不是線段樹的基礎(chǔ)操作
對于第二個操作，如何維護(hù)，其實(shí)線段樹問題中經(jīng)常遇到，對于這種數(shù)值快速遞降至穩(wěn)定的函數(shù)(比如區(qū)間開根號，區(qū)間求歐拉函數(shù))，可以直接暴力修改。像本題中是減去lowbit(x),其實(shí)就是將x二進(jìn)制中的最后一位1刪除，那每個數(shù)最多也就操作個log x次就變成0，因此一共操作次數(shù)只有nlogn次，再加上線段樹操作的復(fù)雜度，也就是$O(nlo{g}^{2}n)$
對于第三個操作，加上$2^k$,k滿足$2^k<=a_i<2^{k+1}$，其實(shí)本質(zhì)就是讓ai的最左邊的1左移一位。也就是說其實(shí)第三個操作只與ai的最高位有關(guān)，且是乘2，乘2這個操作是可以用線段樹實(shí)現(xiàn)的。
具體實(shí)現(xiàn)就是：我們將ai的最高位和剩余位置拆開，sum1記錄的是最高位的情況，sum2記錄是剩余最高位情況，num記錄ai中1的情況，因?yàn)椴僮?是要減去最后一位1，如果num==0，那么sum1和sum2就都等于0。對于操作2，讓sum2-=lowbit(sum2),對于操作3，只需要對sum2進(jìn)行乘2的維護(hù)。查詢時再將sum1和sum2加在一起

代碼：

詳細(xì)看代碼

// Problem: D - Counting Stars // Contest: Virtual Judge - 2021杭電多校第八場 // URL: https://vjudge.net/contest/453140#problem/D // Memory Limit: 131 MB // Time Limit: 4000 ms // Data:2021-08-13 12:59:28 // By Jozky#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; template <typename T> inline void read(T& x) {T f= 1;x= 0;char ch= getchar();while (0 == isdigit(ch)) {if (ch == '-')f= -1;ch= getchar();}while (0 != isdigit(ch))x= (x << 1) + (x << 3) + ch - '0', ch= getchar();x*= f; } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime= clock();freopen("in.txt", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int mod= 998244353; const int maxn= 2e5 + 9; int a[maxn]; int pw[maxn]; struct node {int l, r;ll sum1; //記錄最高位的1ll sum2; //記錄除了最高位剩下的ll num; //記錄二進(jìn)制一共有幾個1ll lazy; //記錄乘2的標(biāo)記 } tr[maxn << 2]; int lg[maxn]; //lg[i]表示a[i]的二進(jìn)制有幾位 int work(int x) { //計算x的二進(jìn)制有幾位int ans= 0;while (x) {ans++;x>>= 1;}return ans; } int work2(int x) { //計算x的二進(jìn)制有幾位是1int ans= 0;while (x) {if (x & 1)ans++;x>>= 1;}return ans; } int lowbit(int x) {return x & (-x); } void pushup(int rt) {tr[rt].sum1= (tr[rt << 1].sum1 + tr[rt << 1 | 1].sum1) % mod;tr[rt].sum2= (tr[rt << 1].sum2 + tr[rt << 1 | 1].sum2) % mod;tr[rt].num= max(tr[rt << 1].num, tr[rt << 1 | 1].num); } void solve(int rt, int val) {tr[rt].sum1= 1ll * tr[rt].sum1 * pw[val] % mod;tr[rt].lazy+= val; } void pushdown(int rt) {solve(rt << 1, tr[rt].lazy);solve(rt << 1 | 1, tr[rt].lazy);tr[rt].lazy= 0; } void build(int rt, int l, int r) {tr[rt].l= l;tr[rt].r= r;tr[rt].lazy= 0;if (l == r) {tr[rt].num= work2(a[l]);tr[rt].sum1= (a[l] & (1 << (lg[l] - 1)));tr[rt].sum2= a[l] - tr[rt].sum1;return;}int mid= (l + r) >> 1;build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);pushup(rt); } void update1(int rt, int l, int r) {if (tr[rt].num == 0)return;if (tr[rt].l > r || tr[rt].r < l)return;if (tr[rt].l == tr[rt].r) {tr[rt].sum2= tr[rt].sum2 - lowbit(tr[rt].sum2);tr[rt].num--;if (tr[rt].num == 0) { //全減沒了tr[rt].sum1= 0;tr[rt].sum2= 0;}return;}pushdown(rt);int mid= (tr[rt].l + tr[rt].r) >> 1;if (l <= mid)update1(rt << 1, l, r);if (r > mid)update1(rt << 1 | 1, l, r);pushup(rt); } void update2(int rt, int l, int r) {if (tr[rt].l > r || tr[rt].r < l)return;if (tr[rt].l >= l && tr[rt].r <= r) {solve(rt, 1);return;}pushdown(rt);int mid= (tr[rt].l + tr[rt].r) >> 1;if (l <= mid)update2(rt << 1, l, r);if (r > mid)update2(rt << 1 | 1, l, r);pushup(rt); } ll query(int rt, int l, int r) {if (tr[rt].l > r || tr[rt].r < l)return 0;if (tr[rt].l >= l && tr[rt].r <= r) {return (1ll * tr[rt].sum1 + tr[rt].sum2) % mod;}pushdown(rt);int mid= (tr[rt].l + tr[rt].r) >> 1;ll ans= 0;if (l <= mid)ans= (ans + query(rt << 1, l, r)) % mod;if (r > mid)ans= (ans + query(rt << 1 | 1, l, r)) % mod;return ans % mod; } int main() {//rd_test();int t;pw[0]= 1;for (int i= 1; i < 200004; i++)pw[i]= 1ll * pw[i - 1] * 2 % mod;scanf("%d", &t);while (t--) {int n;scanf("%d", &n);for (int i= 1; i <= n; i++) {scanf("%d", &a[i]);lg[i]= work(a[i]);}//memset(tr,0,sizeof(tr));build(1, 1, n);int m;read(m);for (int i= 1; i <= m; i++) {int op, l, r;scanf("%d%d%d", &op, &l, &r);if (op == 1)printf("%d\n", query(1, l, r));else if (op == 2)update1(1, l, r);else if (op == 3)update2(1, l, r);}}return 0;//Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的D - Counting Stars HDU - 7059的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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