fork download
copy 
  1. #include<climits>
  2. #include<cstdio>
  3. #include<memory>
  4. #include<random>
  5. #include<set>
  6. #include<tuple>
  7. using namespace std;
  8. using ll = long long;
  9. constexpr ll P = 1000000007;
  10.  
  11. // R = Z_P[x] / (x^3-x^2-x-1)
  12. struct R{
  13.     // ax^2 + bx + c
  14.     ll a, b, c;
  15.     R() noexcept = default;
  16.     constexpr R(ll a, ll b, ll c) noexcept: a((a%P+P)%P), b((b%P+P)%P), c((c%P+P)%P){}
  17.     constexpr R operator *(R const &g) noexcept{
  18.         ll a4 = a*g.a, a3 = a*g.b+b*g.a, a2 = a*g.c+b*g.b+c*g.a, a1 = b*g.c+c*g.b, a0 = c*g.c;
  19.         return {2*a4+a3+a2, 2*a4+a3+a1, a4+a3+a0};
  20.     }
  21.     constexpr R &operator *=(R const &g) noexcept{
  22.         return *this = *this * g;
  23.     }
  24. };
  25.  
  26. tuple<ll, ll, ll> f(long n) noexcept{
  27.     R xp(0, 1, 0), xn(0, 0, 1);
  28.     for(; n; n>>=1){
  29.         if(n&1) xn *= xp;
  30.         xp *= xp;
  31.     }
  32.     return {xn.a, (xn.a+xn.b)%P, (2*xn.a+xn.b+xn.c)%P};
  33. }
  34.  
  35. tuple<ll, ll, ll, ll> loli(ll ll1, ll lr1, ll rl1, ll rr1, ll ll2, ll lr2, ll rl2, ll rr2) noexcept{
  36.     return {
  37.         (ll1*ll2+lr1*ll2+lr1*rl2)%P,
  38.         (ll1*lr2+lr1*lr2+lr1*rr2)%P,
  39.         (rl1*ll2+rr1*ll2+rr1*rl2)%P,
  40.         (rl1*lr2+rr1*lr2+rr1*rr2)%P
  41.     };
  42. }
  43.  
  44. struct Node{
  45.     static mt19937_64 rand;
  46.     long key;
  47.     decltype(rand()) fix = rand();
  48.     ll nll, nlr, nrl, nrr;
  49.     ll subtll, subtlr, subtrl, subtrr;
  50.     shared_ptr<Node> lch, rch;
  51.     Node() noexcept = default;
  52.     Node(long key, ll nll, ll nlr, ll nrl, ll nrr) noexcept: key(key), nll(nll), nlr(nlr), nrl(nrl), nrr(nrr), subtll(nll), subtlr(nlr), subtrl(nrl), subtrr(nrr){}
  53.     void maintain() noexcept{
  54.         subtll = nll, subtlr = nlr, subtrl = nrl, subtrr = nrr;
  55.         if(lch){
  56.             tie(subtll, subtlr, subtrl, subtrr) = loli(lch->subtll, lch->subtlr, lch->subtrl, lch->subtrr, subtll, subtlr, subtrl, subtrr);
  57.         }
  58.         if(rch){
  59.             tie(subtll, subtlr, subtrl, subtrr) = loli(subtll, subtlr, subtrl, subtrr, rch->subtll, rch->subtlr, rch->subtrl, rch->subtrr);
  60.         }
  61.     }
  62. };
  63. mt19937_64 Node::rand(random_device{}());
  64. using Subt = shared_ptr<Node>;
  65. Subt merge(Subt p, Subt q) noexcept{
  66.     if(!p) return q;
  67.     if(!q) return p;
  68.     if(p->fix < q->fix) swap(p, q);
  69.     if(q->key < p->key) p->lch = merge(p->lch, q);
  70.     else p->rch = merge(p->rch, q);
  71.     p->maintain();
  72.     return p;
  73. }
  74. pair<Subt, Subt> split(Subt p, long th) noexcept{
  75.     if(!p) return {nullptr, nullptr};
  76.     if(th >= p->key){
  77.         Subt q, r;
  78.         tie(q, r) = split(p->rch, th);
  79.         p->rch = q;
  80.         p->maintain();
  81.         return {p, r};
  82.     }
  83.     Subt q, r;
  84.     tie(q, r) = split(p->lch, th);
  85.     p->lch = r;
  86.     p->maintain();
  87.     return {q, p};
  88. }
  89. void update(Subt p, long key, ll nll, ll nlr, ll nrl, ll nrr) noexcept{
  90.     if(!p) return;
  91.     if(key == p->key){
  92.         p->nll = nll, p->nlr = nlr, p->nrl = nrl, p->nrr = nrr;
  93.     }else if(key < p->key){
  94.         update(p->lch, key, nll, nlr, nrl, nrr);
  95.     }else{
  96.         update(p->rch, key, nll, nlr, nrl, nrr);
  97.     }
  98.     p->maintain();
  99. }
  100. void increment_key(Subt p, long key, bool dk) noexcept{
  101.     if(!p) return;
  102.     if(key == p->key){
  103.         if(dk){
  104.             ++p->key;
  105.             p->nll = p->nlr;
  106.             p->nrl = p->nrr;
  107.         }
  108.         p->nlr = p->nrr = 0;
  109.     }else if(key < p->key){
  110.         increment_key(p->lch, key, dk);
  111.     }else{
  112.         increment_key(p->rch, key, dk);
  113.     }
  114.     p->maintain();
  115. }
  116. tuple<long, ll, ll, ll, ll> query(Subt p, long th) noexcept{
  117.     if(!p) return {-1, 0, 0, 0, 0};
  118.     if(th < p->key){
  119.         return query(p->lch, th);
  120.     }
  121.     ll a=p->nll, b=p->nlr, c=p->nrl, d=p->nrr;
  122.     if(p->lch){
  123.         tie(a, b, c, d) = loli(p->lch->subtll, p->lch->subtlr, p->lch->subtrl, p->lch->subtrr, a, b, c, d);
  124.     }
  125.     long key = p->key;
  126.     auto t = query(p->rch, th);
  127.     if(get<0>(t) == -1){
  128.         return {key, a, b, c, d};
  129.     }
  130.     tie(a, b, c, d) = loli(a, b, c, d, get<1>(t), get<2>(t), get<3>(t), get<4>(t));
  131.     return {get<0>(t), a, b, c, d};
  132. }
  133.  
  134. int main(){
  135.     long q, bound=LONG_MAX;
  136.     scanf("%*d%ld", &q);
  137.     Subt bst;
  138.     set<long> black;
  139.     while(q--){
  140.         long op, k;
  141.         scanf("%ld%ld", &op, &k);
  142.         if(op == 0){
  143.             if(k>bound || black.find(k)!=black.end()){
  144.                 puts("0"); continue;
  145.             }
  146.             if(!bst || k<*black.begin()){
  147.                 printf("%lld\n", get<2>(f(k)));
  148.                 continue;
  149.             }
  150.             auto t = query(bst, k);
  151.             auto u = f(k-get<0>(t)-1);
  152.             ll ans = (get<3>(t)*get<2>(u)+get<4>(t)*get<2>(u)+get<4>(t)*get<1>(u))%P;
  153.             printf("%lld\n", ans);
  154.         }else{
  155.             auto p = black.insert(k);
  156.             if(!p.second) continue;
  157.             if(k > bound) continue;
  158.             auto it = p.first;
  159.             if(it!=black.begin() && *prev(it)==k-1){
  160.                 if(prev(it)!=black.begin() && *prev(it, 2)==k-2){
  161.                     bound = k-3;
  162.                     bst = split(bst, bound).first;
  163.                     continue;
  164.                 }
  165.                 if(next(it)!=black.end() && *next(it)==k+1){
  166.                     bound = k-2;
  167.                     bst = split(bst, bound).first;
  168.                     continue;
  169.                 }
  170.                 if(++it != black.end()){
  171.                     auto t = f(*it-k-2);
  172.                     if(next(it)!=black.end() && *next(it)==*it+1){
  173.                         update(bst, *it+1, get<2>(t), 0, get<1>(t), 0);
  174.                     }else{
  175.                         update(bst, *it, get<1>(t), get<2>(t), get<0>(t), get<1>(t));
  176.                     }
  177.                 }
  178.                 increment_key(bst, k-1, true);
  179.             }else if(next(it)!=black.end() && *next(it)==k+1){
  180.                 if(next(it, 2)!=black.end() && *next(it, 2)==k+2){
  181.                     bound = k-1;
  182.                     bst = split(bst, bound).first;
  183.                     continue;
  184.                 }
  185.                 increment_key(bst, k+1, false);
  186.             }else{
  187.                 if(++it != black.end()){
  188.                     auto t = f(*it-k-2);
  189.                     if(next(it)!=black.end() && *next(it)==*it+1){
  190.                         update(bst, *it+1, get<2>(t), 0, get<1>(t), 0);
  191.                     }else{
  192.                         update(bst, *it, get<1>(t), get<2>(t), get<0>(t), get<1>(t));
  193.                     }
  194.                 }
  195.                 if(--it == black.begin()){
  196.                     auto t = f(k-1);
  197.                     Subt p, q;
  198.                     tie(p, q) = split(bst, k);
  199.                     bst = merge(merge(p, make_shared<Node>(k, 0, 0, get<1>(t), get<2>(t))), q);
  200.                 }else{
  201.                     auto t = f(k-*prev(it)-2);
  202.                     Subt p, q;
  203.                     tie(p, q) = split(bst, k);
  204.                     bst = merge(merge(p, make_shared<Node>(k, get<1>(t), get<2>(t), get<0>(t), get<1>(t))), q);
  205.                 }
  206.             }
  207.         }
  208.     }
  209. }
  210.  
Success #stdin #stdout 0s 15256KB
comments (?)
stdin
copy 
10 7
0 1
0 2
0 3
0 10
1 3
0 2
0 4
stdout
copy 
1
2
4
274
2
3
https://ideone.com/QfkHpv
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!