Posted 03/25/2016Updated 12/16/2025 Semprathlon / Simfae Dean ACM-ICPC / Programing4 minutes read (About 558 words)

Turing Tree

Time Limit: 6000/3000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

Problem Description

After inventing Turing Tree, 3xian always felt boring when solving problems about intervals, because Turing Tree could easily have the solution. As well, wily 3xian made lots of new problems about intervals. So, today, this sick thing happens again…

Now given a sequence of N numbers A1, A2, …, AN and a number of Queries(i, j) (1≤i≤j≤N). For each Query(i, j), you are to caculate the sum of distinct values in the subsequence Ai, Ai+1, …, Aj.

Input

The first line is an integer T (1 ≤ T ≤ 10), indecating the number of testcases below.
For each case, the input format will be like this:

Line 1: N (1 ≤ N ≤ 30,000).
Line 2: N integers A1, A2, …, AN (0 ≤ Ai ≤ 1,000,000,000).
Line 3: Q (1 ≤ Q ≤ 100,000), the number of Queries.
Next Q lines: each line contains 2 integers i, j representing a Query (1 ≤ i ≤ j ≤ N).

Output

For each Query, print the sum of distinct values of the specified subsequence in one line.

Sample Input

2
3
1 1 4
2
1 2
2 3
5
1 1 2 1 3
3
1 5
2 4
3 5

Sample Output

1
5
6
3
6

Author

3xian@GDUT

离线化
从左到右处理原数列
对询问排序

不再是难题。

/* 
 * File:   main.cpp
 * Author: semprathlon
 *
 * Created on March 25, 2016, 4:02 PM
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int maxn = 100010;

struct SegTree {
    int l, r, m;
    ll val;
    SegTree *L, *R;

    SegTree() {}

    SegTree(int x, int y) {
        this->build(x, y);
    }
    
    ~SegTree(){
        if (this->L!=NULL) free(this->L);
        if (this->R!=NULL) free(this->R);
    }

    void build(int x, int y) {
        int mi = (x + y) >> 1;
        l = x;r = y;m = mi;val = 0;
        if (x < y) {
            L = new SegTree(x, m);
            R = new SegTree(m + 1, y);
        }
    }
    
    inline void up(){
        val=L->val+R->val;
    }
    
    void add(int x, int v) {
        if (l == r) {
            val += v;
            return;
        }
        if (x <= m)
            L->add(x, v);
        else if (x > m)
            R->add(x, v);
        up();
    }

    ll query(int x, int y) {
        if (x <= l && r <= y) {
            return val;
        }
        ll res = 0;
        if (x <= m)
            res += L->query(x, y);
        if (y > m)
            res += R->query(x, y);
        return res;
    }
} *ST;

struct Inv {
    int l, r, id;

    Inv() {};

    Inv(int _l, int _r, int _id) : l(_l), r(_r), id(_id) {};
};

inline bool operator<(const Inv& a, const Inv& b) {
        return a.r < b.r;
}


int a[maxn];
ll ans[maxn];

vector v;

vector::iterator it;

map mp;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, q;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        v.clear();
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            v.push_back(Inv(x, y, i));
        }
        sort(v.begin(), v.end());
        it = v.begin();
        ST = new SegTree(1, n);
        fill(ans, ans + q, 0);
        mp.clear();
        for (int i = 1; i <= n; i++) {
            if (mp.find(a[i])!=mp.end()){
                ST->add(mp[a[i]], -a[i]);
            }
            mp[a[i]]=i;
            ST->add(i, a[i]);
            for (; it != v.end() && it->r == i; it++)
                ans[it->id] = ST->query(it->l, it->r);
        }
        for (int i = 0; i < q; i++)
            printf("%I64d\n", ans[i]);
        free(ST);
    }
    return 0;
}

Posted 03/24/2016Updated 12/16/2025 Semprathlon / Simfae Dean Developing / Server / Weba few seconds read (About 54 words)

【160324】服务器管理记录

Run an existing MySQL-dump script

source [filename]

switch Ubuntu mirror source

(take an eye on the version)

sudo cp /etc/apt/sources.list /etc/apt/sources.list_backup
(editing /etc/apt/sources.list)
sudo apt-get update
sudo apt-get upgrade

http://askubuntu.com/questions/645236/command-to-list-all-users-with-their-uid

Posted 03/19/2016Updated 12/16/2025 Semprathlon / Simfae Dean Abouta few seconds read (About 0 words)

Microsoft Surface 3

Posted 03/19/2016Updated 12/16/2025 Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 491 words)

BestCoder

已解决题目列表
King’s Cake
King’s Phone
King’s Order
King’s Game

Posted 03/05/2016Updated 12/16/2025 Semprathlon / Simfae Dean About4 minutes read (About 529 words)

【非真实】午后静思：量子信息传递，时空穿越？

今天午休时回忆起了《星际穿越》的震撼情节，产生了一些遐想。

量子通信具有无限辽阔的前景？
通过发挥我的主观能动性对过去做出一些改变？

在我高中时期异彩纷呈的种种兴趣爱好中，密码学占有一个旮旯。
那之前就对摩尔斯电码略有一点知晓。甚至有一次从网上摘抄了摩尔斯密码对照表，继而在学校里的通用技术等“闲课”（高二）上鼓捣编解码。
我也长期拥有手表，甚至一块从高二一直使用到现在（大二）的机械手表。
以上是否会构成秘密通信的渠道？

高二是高中五大学科竞赛全线开战的一年。高三是自主招生、三位一体招生在接上高考的轮番作战的一年。
我一如既往地凭借“女生的专长”——记忆和归纳能力勇往直前，却没能摆脱本属于“男生的优势”的推理和演绎能力的顽固缺陷。
化学生物进展顺利，数学物理一筹莫展。
这种格局一直延续到临近高考时仍难以改观。

加入数学、物理竞赛是无所畏惧的探险，然而甚至得不到一个普通的结果。
我意欲以当前的雄厚经验累积，向当年出征前的自己发出信号：数理应由攻转防，腾出宝贵的生产力强化优势方向，还要稳固动荡的根基。
（至少现在看来）高三中后期的颓势都可逆转，进入985高校就真的不是空话。

不过以上并不能提供消极回避现实的机会。
毕竟也要做好准备，在急求向过去发送讯息的同时，接收未来传回的关键情报。

Posted 02/26/2016Updated 12/16/2025 Semprathlon / Simfae Dean Developing / Server / Weba few seconds read (About 84 words)

【160226】服务器管理记录

Test nginx.conf

/usr/sbin/nginx -t
Duplicate a MySQL database with its tables

mysqldump [existing database] -u root -p’[password]’ –add-drop-table | mysql [new database] -u root -p’[password]’
Check the direction of MySQL data files

show variables like ‘%dir%’;
Uninstall and reinstall node & npm

sudo apt-get update
sudo apt-get install nodejs
sudo apt-get install npm

Posted 02/22/2016Updated 12/16/2025 Semprathlon / Simfae Dean Developing / Weba few seconds read (About 15 words)

针对js,jquery中的this对象的理解

详解js和jquery里的this关键字

Posted 02/21/2016Updated 12/16/2025 Semprathlon / Simfae Dean ACM-ICPC / Programing2 minutes read (About 369 words)

BestCoder

已解决题目列表
Rikka with Chess
Rikka with Graph

Posted 02/21/2016Updated 12/16/2025 Semprathlon / Simfae Dean Developing / Server / Weba few seconds read (About 103 words)

【160221】服务器管理记录

MySQL:show columns of a certain datatable:

show full columns from [tablename];
Nginx:remove root directory

root /usr/share/nginx/html;
…
location / {
…
fastcgi_param SCRIPT_FILENAME /usr/share/nginx/html$fastcgi_script_name;
…
}

/etc/init.d/nginx restart
Nginx:add rewrite rules for redirecting,map port 8080 into 80.

server {
listen 8080;
server_name localhost_redirect;
rewrite ^/(.+)/.* /$1 last;
location / {
proxy_pass http://127.0.0.1:80;
proxy_set_header Host $host:80;
proxy_set_header X-Real-IP $remote_addr;
proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
}
}

Posted 02/16/2016Updated 12/16/2025 Semprathlon / Simfae Dean OSa minute read (About 128 words)

黑苹果折腾第三迭代之末

通过不断调换SSDT存档，得出调查结论：
不同于以往的OS X 10.9，现在无论是BIOS还是DSDT或是SSDT屏蔽独显，都会导致核显工作不正常（闪烁、花屏乃至死机）。
独显虽无法参与工作，但也未必是个累赘。
反倒是**sensors.kext系列让机器温度偏高。
睡眠、唤醒顺利，但是蓝牙还是容易停止工作。
USB3.0能轻松驱动。

Turing Tree

Problem Description

Input

Output

Sample Input

Sample Output

Author

Categories

Tags

Subscribe for updates

Links