Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
- */
- #include <cstdio>
- #include <cstring>
- #include <vector>
- #include <algorithm>
- using namespace std;
- #define forn(i, n) for (int i = 0; i < (int)(n); i++)
- #define pb push_back
- #define mp make_pair
- #define all(a) (a).begin(), (a).end()
- typedef long long ll;
- const int N = 3e5;
- int n, m, a[N], l[N], r[N];
- ll ans[N];
- struct Event {
- ll x;
- int i, type;
- bool operator < ( const Event &e ) const { return mp(x, type) < mp(e.x, e.type); }
- };
- vector<Event> e;
- template<const int N>
- struct Fenwick {
- int n;
- ll sum[N];
- void clear() {
- memset(sum, 0, sizeof(sum));
- }
- void add( int y, int d ) {
- for (int x = y; x < N; x |= x + 1)
- sum[x] += d;
- }
- ll get( int x ) {
- ll r = 0;
- for (; x >= 0; x &= x + 1, x--)
- r += sum[x];
- return r;
- }
- ll get( int l, int r ) {
- return get(r) - get(l - 1);
- }
- };
- Fenwick<N> f;
- inline int readChar();
- template <class T = int> inline T readInt();
- template <class T> inline void writeInt( T x, char end = 0 );
- inline void writeChar( int x );
- inline void flush();
- void solve() {
- n = readInt();
- m = readInt();
- forn(i, n) a[i] = readInt();
- forn(i, m) {
- l[i] = readInt() - 1;
- r[i] = readInt() - 1;
- ans[i] = 1;
- }
- forn(_, 50) {
- e.clear();
- forn(i, n) e.pb({a[i], i, 0});
- forn(i, m) e.pb({ans[i], i, 1});
- sort(all(e));
- f.clear();
- for (auto x : e)
- if (x.type == 0)
- f.add(x.i, a[x.i]);
- else
- ans[x.i] = f.get(l[x.i], r[x.i]) + 1;
- }
- forn(i, m) writeInt(ans[i], '\n');
- flush();
- }
- int main() {
- solve();
- }
- /** Read */
- static const int buf_size = 4096;
- inline int getChar() {
- static char buf[buf_size];
- static int len = 0, pos = 0;
- if (pos == len)
- pos = 0, len = fread(buf, 1, buf_size, stdin);
- if (pos == len)
- return -1;
- return buf[pos++];
- }
- inline int readChar() {
- int c = getChar();
- while (c <= 32)
- c = getChar();
- return c;
- }
- template <class T>
- inline T readInt() {
- int s = 1, c = readChar();
- T x = 0;
- if (c == '-')
- s = -1, c = getChar();
- while ('0' <= c && c <= '9')
- x = x * 10 + c - '0', c = getChar();
- return s == 1 ? x : -x;
- }
- /** Write */
- static int write_pos = 0;
- static char write_buf[buf_size];
- inline void writeChar( int x ) {
- if (write_pos == buf_size)
- fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
- write_buf[write_pos++] = x;
- }
- inline void flush() {
- if (write_pos)
- fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
- }
- template <class T>
- inline void writeInt( T x, char end ) {
- if (x < 0)
- writeChar('-'), x = -x;
- char s[24];
- int n = 0;
- while (x || !n)
- s[n++] = '0' + x % 10, x /= 10;
- while (n--)
- writeChar(s[n]);
- if (end)
- writeChar(end);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement