[Ynoi2011]初始化题解

第一道Ynoi，纪念一下。

众所周知，Ynoi会进行惨无人道的卡常操作，所以我们可以使用暴力去做Ynoi。

于是乎，我们考虑分块+暴力。

对于操作2，不难发现是道裸的分块，可以抄P3372的代码。

对于操作1，我们秉持暴力的思想，直接暴力修改。

然后就AC了。

但是如果每个操作都是1 1 1 1，那么最坏复杂度是 \(O(n^2)\) ...

可是毕竟数据不是lxl造的，随便暴力。

卡常都不用卡。

复杂度什么的全部不管。

好像线段树和树状数组被卡掉了？

分块能过就行。

最后贴一下分块的代码。

#include<stdio.h>

#include<math.h>

#define reg register

#define ri reg int

#define rep(i, x, y) for(ri i = x; i <= y; ++i)

#define nrep(i, x, y) for(ri i = x; i >= y; --i)

#define DEBUG 1

#define ll long long

#define il inline

#define max(i, j) (i) > (j) ? (i) : (j)

#define min(i, j) (i) < (j) ? (i) : (j)

#define read(i) io.READ(i)

#define print(i) io.WRITE(i)

#define push(i) io.PUSH(i)

struct IO {

#define MAXSIZE (1 << 20)

#define isdigit(x) (x >= '0' && x <= '9')

  char buf[MAXSIZE], *p1, *p2;

  char pbuf[MAXSIZE], *pp;

#if DEBUG

#else

  IO() : p1(buf), p2(buf), pp(pbuf) {}

  ~IO() {

    fwrite(pbuf, 1, pp - pbuf, stdout);

  }

#endif

  inline char gc() {

#if DEBUG

    return getchar();

#endif

    if(p1 == p2)

      p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);

    return p1 == p2 ? ' ' : *p1++;

  }

  inline bool blank(char ch) {

    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';

  }

  template <class T>

  inline void READ(T &x) {

    register double tmp = 1;

    register bool sign = 0;

    x = 0;

    register char ch = gc();

    for(; !isdigit(ch); ch = gc())

      if(ch == '-') sign = 1;

    for(; isdigit(ch); ch = gc())

      x = x * 10 + (ch - '0');

    if(ch == '.')

      for(ch = gc(); isdigit(ch); ch = gc())

        tmp /= 10.0, x += tmp * (ch - '0');

    if(sign) x = -x;

  }

  inline void READ(char *s) {

    register char ch = gc();

    for(; blank(ch); ch = gc());

    for(; !blank(ch); ch = gc())

      *s++ = ch;

    *s = 0;

  }

  inline void READ(char &c) {

    for(c = gc(); blank(c); c = gc());

  }

  inline void PUSH(const char &c) {

#if DEBUG

    putchar(c);

#else

    if(pp - pbuf == MAXSIZE) {

      fwrite(pbuf, 1, MAXSIZE, stdout);

      pp = pbuf;

    }

    *pp++ = c;

#endif

  }

  template <class T>

  inline void WRITE(T x) {

    if(x < 0) {

      x = -x;

      PUSH('-');

    }

    static T sta[35];

    T top = 0;

    do {

      sta[top++] = x % 10;

      x /= 10;

    } while(x);

    while(top)

      PUSH(sta[--top] + '0');

  }

  template <class T>

  inline void WRITE(T x, char lastChar) {

    WRITE(x);

    PUSH(lastChar);

  }

} io;

ll n, m, a[200010], belong[200010];

ll s, c, st[50010], ed[50010];

ll sum[50010];

void pretreat() {

  s = (int)sqrt(n);

  for(ri i = 1; i <= n; i += s) {

    st[++c] = i;

    ed[c] = min(i + s - 1, n);

  } /*做出每个块的左右端点*/

  rep(i, 1, c) rep(j, st[i], ed[i]) {

    belong[j] = i;

    sum[i] += a[j]; /*预处理块内各数之和*/

  }

  /*记录每一个数在哪一块*/

}

il void single_upd(ll x, ll k) {

  a[x] += k; /*单点增加*/

  sum[belong[x]] += k;

}

il void range_upd(ll x, ll y, ll k) {

  for(ll i = y; i <= n; i += x) single_upd(i, k);

}

il ll range_query(ll x, ll y) {

  ll l = belong[x], r = belong[y], ans = 0;

  if(l == r) {

    rep(i, x, y) ans += a[i];

    return ans % (int)(1e9 + 7);

  }

  rep(i, x, ed[l]) ans += a[i];

  /*左边不完整块的求和*/

  rep(i, st[r], y) ans += a[i];

  rep(i, l + 1, r - 1) ans += sum[i];

  return ans % (int)(1e9 + 7);

}

int main() {

  read(n), read(m);

  rep(i, 1, n) read(a[i]);

  pretreat();

  rep(i, 1, m) {

    ri opt, l, r, c;

    read(opt), read(l), read(r);

    if(opt == 1) read(c), range_upd(l, r, c);

    else print(range_query(l, r)), push('\n');

  }

  return 0;

}

巴特西

[Ynoi2011]初始化题解

最新文章

热门文章

巴特西

[Ynoi2011]初始化 题解

最新文章

热门文章

[Ynoi2011]初始化题解