結果
問題 | No.151 セグメントフィッシング |
ユーザー |
👑 |
提出日時 | 2023-05-30 13:35:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 5,000 ms |
コード長 | 3,244 bytes |
コンパイル時間 | 873 ms |
コンパイル使用メモリ | 78,596 KB |
最終ジャッジ日時 | 2025-02-13 16:31:00 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 19 |
ソースコード
#include <iostream>#include <vector>using namespace std;template< typename T, typename F>struct SegmentTree{private:int n;vector<T> node;F f;T initer;public:SegmentTree(int n_, F f, T initer) : f(f),initer(initer) {n = 1;while(n < n_)n*=2;node.resize(2*n-1, initer);}SegmentTree(int n_, F f,T initer, vector<T> x) : f(f),initer(initer) {n = 1;while(n < n_)n*=2;node.resize(2*n-1, initer);set(x);}void set(vector<T> x){for(int i = 0; n > i; i++){update(i,x[i]);}}void update(int x, T val){x += (n-1);node[x] = val;while(x > 0){x = (x-1)/2;node[x] = f(node[2*x+1],node[2*x+2]);}}void add(int x, T val){x += (n-1);node[x] += val;while(x > 0){x = (x-1)/2;node[x] = f(node[2*x+1],node[2*x+2]);}}T getf(int a,int b, int k=0, int l=0, int r=-1){if(r < 0){r = n-1;}if(r < a || b < l){return initer;}if(a <= l && r <= b){return node[k];}T vl = getf(a,b,2*k+1,l,(l+r)/2);T vr = getf(a,b,2*k+2,(l+r)/2+1,r);return f(vl,vr);}};template <typename T, typename F>SegmentTree<T, F> get_segment_tree(int N, const F &f, T initer){return SegmentTree<T,F>{N,f,initer};}template <typename T, typename F>SegmentTree<T, F> get_segment_tree(int N, const F &f, T initer, vector<T> x){return SegmentTree<T,F>{N,f,initer,x};}int main(){int n,q;cin>>n>>q;auto l = get_segment_tree(n*2, [](long long a, long long b){return a+b;}, 0LL);auto r = get_segment_tree(n*2, [](long long a, long long b){return a+b;}, 0LL);for(int i = 0; q > i; i++){string s;cin>>s;if(s == "L"){long long y,z;cin>>y>>z;int nwi = (y+i)%(n*2);//cout << nwi << endl;l.add(nwi,z);}else if(s == "R"){long long y,z;cin>>y>>z;int nwi = ((y-i)%(n*2)+(n*2))%(n*2);//cout << nwi << endl;r.add(nwi, z);}else{int y,z;cin>>y>>z;z--;//lpair<int,int> lf = {(y+i)%(n*2), (z+i)%(n*2)};long long ans = 0;if(lf.first <= lf.second){ans += l.getf(lf.first, lf.second);}else{ans += l.getf(lf.first, 2*n-1);ans += l.getf(0, lf.second);}pair<int,int> ls = {((n+i-1-z)+n)%(n*2), ((n+i-1-y)+n)%(n*2)};if(ls.first <= ls.second){ans += l.getf(ls.first, ls.second);}else{ans += l.getf(ls.first, 2*n-1);ans += l.getf(0, ls.second);}pair<int,int> rf = {(((y-i)%(n*2))+(n*2))%(n*2), (((z-i)%(n*2))+(n*2))%(n*2)};if(rf.first <= rf.second){ans += r.getf(rf.first, rf.second);}else{ans += r.getf(rf.first, 2*n-1);ans += r.getf(0, rf.second);}pair<int,int> rs = {((((n-i-1-z)+n)%(n*2)) + (n*2))%(n*2), ((((n-i-1-y)+n)%(n*2))+(n*2))%(n*2)};if(rs.first <= rs.second){ans += r.getf(rs.first, rs.second);}else{ans += r.getf(rs.first, 2*n-1);ans += r.getf(0, rs.second);}cout << ans << endl;}}}