Dowemo
0 0 0 0

Every day there are 10 million logins, when users log out, will output login time and log out time, average line length is 1 hours, how to quickly calculate the number o.

Idea: can be processed by line tree. After knowing ( logintime, logouttime ), add the interval ( logintime, logouttime-1 ) to 1.

The specific line tree code is as follows:

#pragma once
const int N = 2 * 24 * 3600;
#define LSON(o) (o <<1)
#define RSON(o) ((o <<1) + 1)
class Node
{
public:
 void setNode(int l, int r, int add, int sum)
 {
 this->l = l;
 this->r = r;
 this->add = add;
 this->sum = sum;
 }
private:
 friend class RMQ;
 int l, r;
 int add;
 int sum;
};
Node node[N];
class RMQ
{
public:
 RMQ()
 {
 tree = node;
 }
 void build(int o, int left, int right)
 {
 if (left == right)
 {
 tree[o].setNode(left, right, 0, 0);
 }
 else
 {
 int mid = (left + right)>> 1;
 build(o * 2, left, mid);
 build(o * 2 + 1, mid + 1, right);
 tree[o].l = left; tree[o].r = right; tree[o].add = 0; tree[o].sum = 0;
 }
 }
 void update(int o, int left, int right, int v)
 {
 if (left <= tree[o].l && right> = tree[o].r)
 {
 tree[o].add += v;
 }
 else
 {
 int mid = (tree[o].l + tree[o].r)>> 1;
 if (left <= mid) update(LSON(o), left, right, v);
 if (right> mid) update(RSON(o), left, right, v);
 }
 maintain(o);
 }
 int query(int o, int left, int right, int add)
 {
 if (left <= tree[o].l && right> = tree[o].r)
 {
 return tree[o].sum + add * (tree[o].r - tree[o].l + 1);
 }
 else
 {
 int mid = (tree[o].l + tree[o].r)>> 1;
 int result = 0;
 if (left <= mid)
 {
 result += query(LSON(o), left, right, add + tree[o].add);
 }
 if (right> mid)
 {
 result += query(RSON(o), left, right, add + tree[o].add);
 }
 return result;
 }
 }
private:
 void pushdown(int o)
 {
 if (tree[o].add> 0)
 {
 tree[LSON(o)].add += tree[o].add;
 tree[RSON(o)].add += tree[o].add;
 tree[o].add = 0;
 }
 }
 void maintain(int o)
 {
 if (tree[o].r> tree[o].l)
 {
 tree[o].sum = tree[LSON(o)].sum + tree[RSON(o)].sum;
 }
 tree[o].sum += tree[o].add * (tree[o].r - tree[o].l + 1);
 }
 Node* tree;
};





Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs