| 记录编号 |
568566 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HSOI 2019] HS的新题 |
最终得分 |
100 |
| 用户昵称 |
 yrtiop |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.264 s |
| 提交时间 |
2022-01-16 21:15:08 |
内存使用 |
5.25 MiB |
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <cctype>
#include <vector>
#define Chtholly set<node>::iterator
using namespace std;
const int maxn = 100005;
typedef long long ll;
const ll mod = 998244353ll;
struct Nota {
ll d[32];
void clear() {
memset(d , 0 , sizeof(d));
return ;
}
void insert(ll x) {
for(int i = 31;~ i;-- i) {
if(x >> i & 1) {
if(d[i])x ^= d[i];
else {
d[i] = x;
break ;
}
}
}
return ;
}
ll getans() {
ll ans = 0;
for(int i = 31;~ i;-- i) {
ans = max(ans , ans ^ d[i]);
}
return ans % mod;
}
} Seniorious;
struct number {
ll val;
int tot;
number() {
val = tot = 0;
}
number(ll val,int tot):val(val),tot(tot){}
bool operator < (const number& p)const {
return val < p.val;
}
};
int read() {
int s = 0;
char c = getchar();
for(;!isdigit(c);c = getchar());
for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
return s;
}
ll Read() {
ll s = 0;
char c = getchar();
for(;!isdigit(c);c = getchar());
for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
return s;
}
ll power(ll x,ll y) {
ll ans = 1ll;
for(;y;y >>= 1) {
if(y & 1) {
(ans *= x) %= mod;
}
(x *= x) %= mod;
}
return ans % mod;
}
int n,m;
struct node {
int l,r;
mutable ll v;
node() {
l = r = 0;
v = 0;
}
node(int l,int r = 0,ll v = 0):l(l),r(r),v(v){};
bool operator < (const node& p)const {
return l < p.l;
}
};
set<node> s;
Chtholly split(int pos) {
Chtholly it = s.lower_bound(node(pos));
if(it != s.end()&&it -> l == pos) {
return it;
}
-- it;
int l = it -> l;
int r = it -> r;
ll v = it -> v;
s.erase(it);
s.insert(node(l , pos - 1 , v));
return s.insert(node(pos , r , v)).first;
}
void modify_assign(int l,int r,ll x) {
Chtholly itr = split(r + 1),itl = split(l);
s.erase(itl , itr);
s.insert(node(l , r , x));
return ;
}
void modify_opposite(int l,int r) {
Chtholly itr = split(r + 1),itl = split(l);
for(Chtholly it = itl;it != itr;++ it) {
it -> v = power(it -> v , mod - 2ll);
}
return ;
}
void modify_time(int l,int r,ll x) {
Chtholly itr = split(r + 1),itl = split(l);
for(Chtholly it = itl;it != itr;++ it) {
(it -> v *= x) %= mod;
}
return ;
}
int query_value(int l,int r,ll x,ll y) {
int ans = 0;
Chtholly itr = split(r + 1),itl = split(l);
for(Chtholly it = itl;it != itr;++ it) {
if(it -> v >= x&&it -> v <= y)ans += (it -> r) - (it -> l) + 1;
}
return ans;
}
void modify_average(int l,int r) {
ll ans = 0;
Chtholly itr = split(r + 1),itl = split(l);
for(Chtholly it = itl;it != itr;++ it) {
(ans += 1ll * it -> v * (ll)(it -> r - it -> l + 1)) %= mod;
}
s.erase(itl , itr);
s.insert(node(l , r , (ans * power((ll)(r - l + 1) , mod - 2ll)) % mod));
return ;
}
int query_maxsize(int l,int r) {
Chtholly itr = split(r + 1),itl = split(l);
vector<number> a;
for(Chtholly it = itl;it != itr;++ it) {
a.push_back(number(it -> v , it -> r - it -> l + 1));
}
sort(a.begin() , a.end());
int ans_max = 0;
ll ans_val = 0;
for(int i = 0;i < a.size();++ i) {
if(i + 1 < a.size()&&a[i].val == a[i + 1].val) {
a[i + 1].tot += a[i].tot;
continue ;
}
if(a[i].tot > ans_max) {
ans_max = a[i].tot;
ans_val = a[i].val;
}
}
return ans_val;
}
int query_distinct_size(int l,int r) {
Chtholly itr = split(r + 1),itl = split(l);
vector<number> a;
for(Chtholly it = itl;it != itr;++ it) {
a.push_back(number(it -> v , it -> r - it -> l + 1));
}
sort(a.begin() , a.end());
int cnt = 0;
for(int i = 0;i < a.size();++ i) {
if(i + 1 < a.size()&&a[i].val == a[i + 1].val)continue ;
++ cnt;
}
return cnt;
}
ll query_maxxor(int l,int r) {
Seniorious.clear();
Chtholly itr = split(r + 1),itl = split(l);
vector<number> a;
for(Chtholly it = itl;it != itr;++ it) {
a.push_back(number(it -> v , it -> r - it -> l + 1));
}
sort(a.begin() , a.end());
for(int i = 0;i < a.size();++ i) {
if(i + 1 < a.size()&&a[i].val == a[i + 1].val)continue ;
Seniorious.insert(a[i].val);
}
return Seniorious.getans();
}
int main() {
freopen("xfdxt.in","r",stdin);
freopen("xfdxt.out","w",stdout);
n = read();
m = read();
for(int i = 1;i <= n;++ i) {
ll x = Read();
s.insert(node(i , i , x));
}
while(m --) {
int op,l,r;
ll x,y;
op = read();
l = read();
r = read();
if(l > r)swap(l , r);
switch(op) {
case 1: {
x = Read();
modify_assign(l , r , x);
break;
}
case 2: {
modify_opposite(l , r);
break;
}
case 3: {
x = Read();
modify_time(l , r , x);
break;
}
case 4: {
x = Read();
y = Read();
printf("%d\n",query_value(l , r , x , y));
break;
}
case 5: {
modify_average(l , r);
break;
}
case 6: {
printf("%lld\n",query_maxsize(l , r));
break;
}
case 7: {
printf("%d\n",query_distinct_size(l , r));
break;
}
case 8: {
printf("%lld\n",query_maxxor(l , r));
break;
}
}
}
return 0;
}