結果
問題 | No.925 紲星 Extra |
ユーザー |
![]() |
提出日時 | 2019-11-09 00:32:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9,811 ms / 10,000 ms |
コード長 | 2,519 bytes |
コンパイル時間 | 1,248 ms |
コンパイル使用メモリ | 118,172 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 03:21:24 |
合計ジャッジ時間 | 59,164 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<ll, ll> P; int n; vector<ll> seg[500]; vector<ll> sum[500]; const int b=500; vector<ll> a; void update(int x, ll y){ a[x]=y; int t=x/b; for(int i=t*b; i<min((t+1)*b, n); i++){ seg[t][i-t*b]=a[i]; } sort(seg[t].begin(), seg[t].end()); for(int i=0; i<seg[t].size(); i++){ sum[t][i+1]=sum[t][i]+seg[t][i]; } } int count(int l, int r, ll x){ int ret=0; int l1=(l+b-1)/b, r1=r/b; for(int i=l; i<l1*b; i++){ if(a[i]<=x) ret++; if(i==r-1){ return ret; } } for(int i=l1; i<r1; i++){ ret+=upper_bound(seg[i].begin(), seg[i].end(), x)-seg[i].begin(); } for(int i=r1*b; i<r; i++){ if(a[i]<=x) ret++; } return ret; } ll med(int l, int r){ ll al=0, ar=(1ll<<40); int m=(r-l+1)/2; while(ar-al>1){ ll am=(al+ar)>>1; int cnt=count(l, r, am); if(cnt>=m) ar=am; else al=am; } return ar; } ll query(int l, int r){ ll md=med(l, r); ll ret=0; int l1=(l+b-1)/b, r1=r/b; for(int i=l; i<l1*b; i++){ if(a[i]<md) ret+=md-a[i]; else ret+=a[i]-md; if(i==r-1){ return ret; } } for(int i=l1; i<r1; i++){ int k=lower_bound(seg[i].begin(), seg[i].end(), md)-seg[i].begin(); ret+=md*k-sum[i][k]; ret+=sum[i].back()-sum[i][k]-md*(seg[i].size()-k); } for(int i=r1*b; i<r; i++){ if(a[i]<md) ret+=md-a[i]; else ret+=a[i]-md; } return ret; } int main() { int q; cin>>n>>q; a.resize(n); for(int i=0; i<n; i++){ scanf("%lld", &a[i]); a[i]++; seg[i/b].push_back(a[i]); } for(int i=0; i<=(n-1)/b; i++){ sort(seg[i].begin(), seg[i].end()); sum[i].resize(seg[i].size()+1); for(int j=0; j<seg[i].size(); j++){ sum[i][j+1]=sum[i][j]+seg[i][j]; } } ll p1=(1<<16)-1, p2=(1ll<<40)-1; ll s=0; for(int i=0; i<q; i++){ int t; scanf("%d", &t); if(t==1){ int x; ll y; scanf("%d %lld", &x, &y); x^=(s&p1); y^=(s&p2); update(x-1, y+1); }else{ int l, r; scanf("%d %d", &l, &r); l^=(s&p1); r^=(s&p1); if(l>r) swap(l, r); l--; ll ans=query(l, r); printf("%lld\n", ans); s^=ans; } } return 0; }