J. 二进制与、平方和

https://codeforces.com/gym/104095/problem/J

分析操作一

1&0=0 ,0&1=0，ai<=qmi(2,24),说明每个数最多操作25次

维护区间或和，orsum & x== orsum 就不用递归下去了

势能线段树code

// Problem: J. 二进制与、平方和
// Contest: Codeforces - 2020 CCPC Henan Provincial Collegiate Programming Contest
// URL: https://codeforces.com/gym/104095/problem/J
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N=3e5+9;
const int mod=998244353;
int a[N];
template<class T>
constexpr T power(T a, LL b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;
}template<int P>
struct MInt {int x;constexpr MInt() : x{} {}constexpr MInt(LL x) : x{norm(x % getMod())} {}static int Mod;constexpr static int getMod() {if (P > 0) {return P;} else {return Mod;}}constexpr static void setMod(int Mod_) {Mod = Mod_;}constexpr int norm(int x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}constexpr int val() const {return x;}explicit constexpr operator int() const {return x;}constexpr MInt operator-() const {MInt res;res.x = norm(getMod() - x);return res;}constexpr MInt inv() const {assert(x != 0);return power(*this, getMod() - 2);}constexpr MInt &operator*=(MInt rhs) & {x = 1LL * x * rhs.x % getMod();return *this;}constexpr MInt &operator+=(MInt rhs) & {x = norm(x + rhs.x);return *this;}constexpr MInt &operator-=(MInt rhs) & {x = norm(x - rhs.x);return *this;}constexpr MInt &operator/=(MInt rhs) & {return *this *= rhs.inv();}friend constexpr MInt operator*(MInt lhs, MInt rhs) {MInt res = lhs;res *= rhs;return res;}friend constexpr MInt operator+(MInt lhs, MInt rhs) {MInt res = lhs;res += rhs;return res;}friend constexpr MInt operator-(MInt lhs, MInt rhs) {MInt res = lhs;res -= rhs;return res;}friend constexpr MInt operator/(MInt lhs, MInt rhs) {MInt res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {LL v;is >> v;a = MInt(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {return os << a.val();}friend constexpr bool operator==(MInt lhs, MInt rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MInt lhs, MInt rhs) {return lhs.val() != rhs.val();}
};template<>
int MInt<0>::Mod =998244353;template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();constexpr int P =998244353;
using Z = MInt<P>;const int mxn = 2e5 + 10;
struct SNSEG{#define ll long long #define tl(id) (id<<1)#define tr(id) (id<<1|1)#define li inlinestruct node{Z pfval;int orsum;}seg[N<<2];#define pushup(id) seg[id].pfval=seg[tl(id)].pfval+seg[tr(id)].pfval, seg[id].orsum=seg[tl(id)].orsum|seg[tr(id)].orsum;li int inrange(int L,int R,int l,int r){return L>=l && R<=r;}li int outofrange(int L,int R,int l,int r){return L>r || l>R;}li void build(int id,int l,int r){if(l==r){seg[id].pfval=1ll*a[l]*a[l];// seg[id].val=a[l];seg[id].orsum=a[l];return;}int mid=(l+r)>>1;build(tl(id),l,mid);build(tr(id),mid+1,r);pushup(id);}li Z query(int id,int L,int R,int l,int r){if(inrange(L,R,l,r)){return seg[id].pfval;}else if(!outofrange(L,R,l,r)){int mid=(L+R)>>1;return query(tl(id),L,mid,l,r)+query(tr(id),mid+1,R,l,r);}else{return 0;}}li void modify(int id,int L,int R,int l,int r,int x){if(L==R){// seg[id].val&=x;seg[id].orsum&=x;//修改seg[id].pfval=1ll*seg[id].orsum*seg[id].orsum;return;}int mid=(L+R)>>1;if(mid>=l && (seg[tl(id)].orsum&x)!=(seg[tl(id)].orsum)){modify(tl(id),L,mid,l,r,x);}if(mid<r && (seg[tr(id)].orsum&x)!=(seg[tr(id)].orsum)){modify(tr(id),mid+1,R,l,r,x);}pushup(id);}
}t;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}t.build(1,1,n);int q;cin>>q;for(int i=1;i<=q;i++){int op;cin>>op;if(op==1){int l,r,x;cin>>l>>r>>x;t.modify(1,1,n,l,r,x);}else{int l,r;cin>>l>>r;cout<<t.query(1,1,n,l,r)<<'\n';		}// for(int i=1;i<=n;i++){// cout<<t.ask(1,1,n,i)<<" ";// }// cout<<'\n';}return 0;
}