結果
| 問題 |
No.2395 区間二次変換一点取得
|
| コンテスト | |
| ユーザー |
 YocyCraft
|
| 提出日時 | 2023-07-28 21:40:42 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 163 ms / 2,000 ms |
| コード長 | 6,300 bytes |
| コンパイル時間 | 2,539 ms |
| コンパイル使用メモリ | 205,792 KB |
| 最終ジャッジ日時 | 2025-02-15 20:10:43 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
char nl = '\n';
char sp = ' ';
using ll = long long;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using si = unordered_set<int>;
using sl = unordered_set<ll>;
using tsi = set<int>;
using tsl = set<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using tmii = map<int, int>;
using tmll = map<ll, ll>;
using mii = unordered_map<int, int>;
using mll = unordered_map<ll, ll>;
using pqi = priority_queue<int>;
using pqig = priority_queue<int, vi, greater<int>>;
using pql = priority_queue<ll>;
using pqlg = priority_queue<ll, vl, greater<ll>>;
using pqpii = priority_queue<pii>;
using pqpll = priority_queue<pll>;
#define tp3(T) tuple<T,T,T>
#define tp4(T) tuple<T,T,T,T>
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sort_and_unique(a) sort(all(a));(a).resize(unique(all(a))-(a).begin())
#define outrange(x,min,max) ((x)<(min) || (x)>(max))
ll _start_time;
#define nano (chrono::system_clock::now().time_since_epoch().count())
#define reset_timer _start_time=nano
#define chime cout<<((nano-_start_time)/1e9)<<endl
#define init_rng mt19937 rng(nano)
#define randint(a,b) ((a)+rng()%((b)-(a)+1))
#ifndef ONLINE_JUDGE
#define debug(x) (cout<<(#x)<<':'<<(x)<<'\n')
#else
#define debug(x)
#endif
void yesno(bool a) {
cout << (a ? "Yes\n" : "No\n");
}
template<typename L, typename R>
ostream& operator<<(ostream& out, const pair<L, R>& p) {
out << '(' << p.first << ',' << p.second << ')';
return out;
}
template<typename T1, typename T2, typename T3>
ostream& operator<<(ostream& out, const tuple<T1, T2, T3>& tp) {
auto &[t1, t2, t3] = tp;
out << '(' << t1 << ',' << t2 << ',' << t3 << ')';
return out;
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
for (auto &i : v) out << i << ' ';
out << nl;
return out;
}
template<typename T>
ostream& operator<<(ostream& out, const set<T>& v) {
for (auto &i : v) out << i << ' ';
out << nl;
return out;
}
template<typename T>
ostream& operator<<(ostream& out, const unordered_set<T>& v) {
for (auto &i : v) out << i << ' ';
out << nl;
return out;
}
template<typename K, typename V>
ostream& operator<<(ostream& out, const map<K, V>& m) {
out << '[';
for (auto &[k, v] : m) {
out << k << ':' << v << sp;
}
out << "]\n";
return out;
}
template<typename K, typename V>
ostream& operator<<(ostream& out, const unordered_map<K, V>& m) {
out << '[';
for (auto &[k, v] : m) {
out << k << ':' << v << sp;
}
out << "]\n";
return out;
}
namespace segtree_single_point{
#define sti segtree<int>
#define stl segtree<ll>
template<typename T>
auto lambda_add=[](T &x,T &y)->T{
return x+y;
};
template<typename T>
auto lambda_min=[](T &x,T &y)->T{
return x<y?x:y;
};
template<typename T>
auto lambda_max=[](T &x,T &y)->T{
return x>y?x:y;
};
template<typename T>
auto lambda_min_max=[](const pair<T,T> &p1,const pair<T,T> &p2)->pair<T,T>{
return {min(p1.first,p2.first),max(p1.second,p2.second)};
};
template<typename T>
class segtree{
public:
segtree(const vector<T> &source, function<T(T&,T&)> merger, T defaultValue=(T)0){
this->merger=merger;
this->defaultValue=defaultValue;
int n=source.size();
int L=1;
while(L<n) L<<=1;
size=L;
vector<T> v(2*L,defaultValue);
data=v;
for(int i=0;i<n;i++) data[L+i]=source[i];
for(int i=L-1;i>=1;i--) data[i]=merge(data[2*i],data[2*i+1]);
}
T get(int index){
return data[size+index];
}
void add(int index,T value){
put(index,data[size+index]+value);
}
void put(int index,T value){
_put(size+index,value);
}
//查询闭区间[l,r]
T query(int l,int r){
return _query(1,0,size,l,r+1);
}
/*查找在l右边的，离l最远的坐标r，使得query(l,r)满足条件。
需要ok函数满足二分查找性质：即当r>l时，ok(query(l,r))-->ok(query(l,r+1))。
找不到则返回-1。
@param l 二分查找的起点。
@param ok 判断某个区间是否合法的函数。
@return 查找到的在l右边的，离l最远的坐标，使得ok(query(l,r))==true。
如果找不到，返回-1。
*/
int find_from(int l, const function<bool(T)> &ok){
T prev=defaultValue;
return _find_from(1,0,size,l,ok,prev);
}
void show(){
cout<<data;
}
private:
vector<T> data;
function<T(T&,T&)> merger;
int size;
T defaultValue;
T merge(T left,T right){
return merger(left,right);
}
void _put(int i,T value){
data[i]=value;
if(i==1) return;
int j=i^1;
if(i>j) swap(i,j);
_put(i>>1,merge(data[i],data[j]));
}
T _query(int index,int L,int R,int l,int r){
if(L>=r || R<=l) return defaultValue;
// int index=(size+L)/(R-L);
if(index>=size) {
return data[index];
}
if(L>=l && R<=r) {
return data[index];
}
int mid=(L+R)>>1;
T ans=defaultValue;
if(r>L) ans=merge(ans,_query(2*index,L,mid,l,r));
if(l<R) ans=merge(ans,_query(2*index+1,mid,R,l,r));
return ans;
}
int _find_from(int index,int L,int R,int l, const function<bool(T)> &ok,T &prev){
if(R<=l) return -1;
T after_merge=merge(prev,data[index]);
bool this_ok=ok(after_merge);
if(index>=size){
if(this_ok){
prev=after_merge;
return L;
}else return -1;
}
if(L>=l && this_ok) {
prev=after_merge;
return R-1;
}
int mid=(L+R)>>1;
if(mid<=l) return _find_from(2*index+1,mid,R,l,ok,prev);
int ans=-1;
ans=max(ans,_find_from(2*index,L,mid,l,ok,prev));
if(ans==mid-1) {
ans=max(ans,_find_from(2*index+1,mid,R,l,ok,prev));
}
return ans;
}
};
}
using namespace segtree_single_point;
ll mod;
const int MAX=100005;
ll x[MAX];
ll y[MAX];
ll z[MAX];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n,q;
cin>>n>>mod>>q;
x[0]=y[0]=z[0]=1;
for(int i=1;i<MAX;i++){
x[i]=(x[i-1]+1)%mod;
y[i]=(3*y[i-1]+2*x[i]*z[i-1])%mod;
z[i]=(3*z[i-1])%mod;
}
vi v(n+1,0);
sti st(v,lambda_add<int>);
while(q--){
int L,M,R;
cin>>L>>M>>R;
st.add(L,1);
if(R<n) st.add(R+1,-1);
int t=st.query(1,M);
cout<<x[t]<<sp<<y[t]<<sp<<z[t]<<nl;
}
}