Pacific Northwest Region Programming Contest Division 1

（ACM）数据结构----线段树

Problem J Shopping

题意

• 给定a[1...n]表示n个商品的价值。1<=n<=200000
• q次询问。每次询问有v,l,r表示有个人携带v元，从l到r，每次遇到一个商品就买尽可能多，问最后剩下的钱。1<=q<=200000

题解

• 对于每一次购买商品，一定是购买能买的并且最左边的。那么用线段树实现就可以了。

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define de(x) cout << #x << "=" << x << endl
const int N=200005;
ll Min[N<<2];
int id[N<<2];
void UP(int rt) {
    Min[rt]=Min[rt<<1];
    id[rt]=id[rt<<1];
    if( Min[rt<<1|1] < Min[rt] ) {
        Min[rt]=Min[rt<<1|1];
        id[rt]=id[rt<<1|1];
    }
}
//存区间内最小的数和它的id
void build(int l,int r,int rt) {
    if(l==r) {
        scanf("%I64d",Min+rt);
        id[rt]=l;
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    UP(rt);
}
//返回区间小于v的最前面的，区间的数没有小于v返回-1
pli qry(int L,int R,ll v,int l,int r,int rt) {
    pli tt=mp(-1,-1);
    if( R<l || r<L || l>r || L>R || Min[rt]>v ) return tt;
    if(l==r) return mp(Min[rt],id[rt]);
    int m=(l+r)>>1;
    pli t1=qry(L,R,v,lson);
    if(t1!=tt) return t1;
    pli t2=qry(L,R,v,rson);
    return t2;
}
int main() {
    ///
    int n,q;scanf("%d%d",&n,&q);
    ///build
    build(1,n,1);
    while(q--) {
        ll v;int l,r;
        scanf("%I64d%d%d",&v,&l,&r);
        while(1) {
            pli t=qry(l,r,v,1,n,1);
            if(t.fi==-1) break;
            v=v%t.fi;
            l=t.se+1;
            if(l>r) break;
        }
        printf("%I64d\n",v);
    }
    return 0;
}

The sale bin of Big Box Bargains contains n products in a row. The ith item has price ai per unit.There is no limit to the quantity of any item.
There are q customers who will enter the store to buy items. The ith customer has vi dollars, starts at item li and walks to the right to item ri (inclusive), one item at a time.
Each time they encounter an item, they will buy as many units of the item as they can afford.
You are now wondering, for each customer, how much money they will have left after buying items.

Input
The first line of input contains two space-separated integers n and q (1 ≤ n, q ≤ 200,000).
The next line of input contains n space-separated integers ai (1 ≤ ai ≤ 1018).
Each of the next q lines contains three space-separated integers vi (1 ≤ vi ≤ 1018), li , and ri (1 ≤ li ≤ ri ≤ n).

Output
For each of the q customers, print, on a single line, a single integer indicating the remaining amount of money after shopping.

Sample Input
5 3
5 3 2 4 6
8 5 5
107 1 4
7 3 5

Sample Output
2
0
1