結果
| 問題 |
No.3078 Difference Sum Query
|
| コンテスト | |
| ユーザー |
 Rubikun
|
| 提出日時 | 2025-03-28 21:20:19 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,201 bytes |
| コンパイル時間 | 2,541 ms |
| コンパイル使用メモリ | 217,016 KB |
| 実行使用メモリ | 166,688 KB |
| 最終ジャッジ日時 | 2025-03-28 21:20:58 |
| 合計ジャッジ時間 | 37,794 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 TLE * 6 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;
//2d point update rectangle sum
// https://kopricky.github.io/code/SegmentTrees/rangetree_pointupdate.html
template<typename T> class segtree {
private:
int n, sz;
vector<T> node;
public:
void init(const vector<T>& v){
sz = (int)v.size();
n = 1;
while(n < sz){
n *= 2;
}
node.assign(2*n, 0);
for(int i = 0; i < sz; i++){
node[i+n] = v[i];
}
for(int i=n-1; i>=1; i--){
node[i] = node[2*i] + node[2*i+1];
}
}
void update(int k, const T a)
{
node[k+=n] += a;
while(k>>=1){
node[k] = node[2*k] + node[2*k+1];
}
}
T query(int a, int b)
{
T res1 = 0, res2 = 0;
a += n, b += n;
while(a != b){
if(a % 2) res1 = res1 + node[a++];
if(b % 2) res2 = res2 + node[--b];
a >>= 1, b >>= 1;
}
return res1 + res2;
}
void print(){
for(int i = 0; i < sz; i++){
cout << query(i, i+1) << " ";
}
cout << endl;
}
};
//座標の型, 値の型
template<typename CandidateType, typename ValueType> class RangeTree
{
public:
static_assert(std::is_integral<CandidateType>::value, "Integral required.");
private:
using CT = CandidateType;
using VT = ValueType;
using pcc = pair<CT, CT>;
using pci = pair<CT, int>;
int n, sz;
vector<segtree<VT> > seg;
// y座標, x座標
vector<vector<pcc> > yx;
// y座標, x座標
vector<pcc> sorted;
void update_(int id, const CT x, const CT y, const VT val) {
id += n-1;
const int yid = lower_bound(all(yx[id]), pcc(y, x)) - yx[id].begin();
seg[id].update(yid, val);
while(id > 0){
id = (id - 1) / 2;
const int yid = lower_bound(all(yx[id]), pcc(y, x)) - yx[id].begin();
seg[id].update(yid, val);
}
}
VT query(const int lxid, const int rxid, const CT ly, const CT ry, const int k, const int l, const int r) {
if(r <= lxid || rxid <= l) return 0;
if(lxid <= l && r <= rxid){
const int lyid = lower_bound(all(yx[k]), pcc(ly, numeric_limits<CT>::min())) - yx[k].begin();
const int ryid = upper_bound(all(yx[k]), pcc(ry, numeric_limits<CT>::min())) - yx[k].begin();
return (lyid >= ryid) ? 0 : seg[k].query(lyid, ryid);
}else{
return query(lxid, rxid, ly, ry, 2*k+1, l, (l+r)/2) + query(lxid, rxid, ly, ry, 2*k+2, (l+r)/2, r);
}
}
public:
// 座標, 点の値
RangeTree(const vector<pcc>& cand, const vector<VT>& val) : n(1), sz((int)cand.size()), sorted(sz){
while(n < sz) n *= 2;
for(int i = 0; i < sz; ++i){
sorted[i] = {cand[i].first, i};
}
sort(all(sorted), [&](const pcc& a, const pcc& b){
return (a.first == b.first) ? (cand[a.second].second < cand[b.second].second) : (a.first < b.first);
});
yx.resize(2*n-1), seg.resize(2*n-1);
for(int i = 0; i < sz; ++i){
yx[i+n-1] = {{sorted[i].second, sorted[i].first}};
vector<VT> arg = {val[sorted[i].second]};
seg[i+n-1].init(arg);
sorted[i].second = cand[sorted[i].second].second;
}
for(int i = n-2; i >= 0; --i){
yx[i].resize((int)yx[2*i+1].size() + (int)yx[2*i+2].size());
if(yx[i].empty()) continue;
merge(all(yx[2*i+1]), all(yx[2*i+2]), yx[i].begin(), [&](const pcc& a, const pcc& b){
return (cand[a.first].second == cand[b.first].second)
? (a.second < b.second) : (cand[a.first].second < cand[b.first].second);
});
vector<VT> arg((int)yx[i].size());
for(int j = 0; j < (int)yx[i].size(); ++j){
arg[j] = val[yx[i][j].first];
}
seg[i].init(arg);
}
for(int i = 0; i < 2*n-1; ++i){
for(pcc& e : yx[i]){
e.first = cand[e.first].second;
}
}
}
// 点 (x,y) の更新を行う
void update(const CT x, const CT y, const VT val){
const int id = lower_bound(all(sorted), pcc(x, y)) - sorted.begin();
return update_(id, x, y, val);
}
// [lx,rx) × [ly,ry) の長方形領域のクエリに答える
VT query(const CT lx, const CT ly, const CT rx, const CT ry){
const int lxid = lower_bound(all(sorted), pcc(lx, numeric_limits<CT>::min())) - sorted.begin();
const int rxid = upper_bound(all(sorted), pcc(rx, numeric_limits<CT>::min())) - sorted.begin();
return (lxid >= rxid) ? 0 : query(lxid, rxid, ly, ry, 0, 0, n);
}
};
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
ll N,Q;cin>>N>>Q;
vll S(N);
vl A(N),B(N);
for(int i=0;i<N;i++){
ll x;cin>>x;
S[i]=mp(i,x);
A[i]=1;
B[i]=x;
}
RangeTree<ll,ll> CN(S,A),SUM(S,B);
ll M=10000000003LL;
while(Q--){
ll l,r,x;cin>>l>>r>>x;l--;
ll ans=0;
ans+=CN.query(l,0,r,x)*x;
ans-=SUM.query(l,0,r,x);
ans-=CN.query(l,x,r,M)*x;
ans+=SUM.query(l,x,r,M);
cout<<ans<<"\n";
}
}