「2019-08-08 省常中互测」序列

Description

序列$a$原来全为$0$,每次对于一段区间$[l,r]$进行如下操作:

  • l r s e,表示对于区间$[l,r]$每一位加上以$s$开头$e$结尾的等差数列的对应一项的值。

例如1 5 1 9,就是令$a[1]+1,a[2]+3,a[3]+5,a[4]+7,a[5]+9$

让你输出最后序列每一位的异或和。

答案保证不超过long long

Data Range

$n\leq 500000$

Solution

首先我们记$d$为修改操作中等差数列的公差,计算方法为$(e-s)\div (r-l)$。

首先考虑每次修改的本质,我们对加上去的序列进行差分,会发现差分数组每次$+d$,会发现是一个连续相等的区间,作用范围是$[l+1,r+1]$。

然后我们对其做前缀和,就可以得到原序列的一部分差分

因为我们是对差分数组做了差分,所以原序列应该还要在$l$处$s$,在$r+1$处$-e$。

然后对这个差分数列做前缀和就可以得到最终操作的序列了。

Code

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define REP(i, s, t) for (int i = (s), i##ed = (t); i <= i##ed; i ++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
template <typename T> void chkmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T> void chkmin(T &x, T y) {
  x = x < y ? x : y;
}
template <typename T> void read(T &x) {
  x = 0; bool w = 0; char ch = 0;
  for (; !isdigit(ch); ch = getchar()) w |= ch == '-';
  for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
  x *= w ? -1 : 1;
}
template <typename T> void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
template <typename T> void write(T x, char ch) {
  write(x);
  putchar(ch);
}
template <typename T> void writeln(T x) {
  write(x);
  puts("");
}
const int N = 500000 + 5;
ll sum1[N], sum2[N];
ll ans = 0;
int n, m;
int main() {
  read(n); read(m); 
  memset(sum1, 0, sizeof(sum1));
  memset(sum2, 0, sizeof(sum2));
  sum2[0] = 0; 
  while (m --) {
    int l, r; read(l); read(r); 
    ll s, e; read(s); read(e);
    ll d = (e - s) / (r - l);
    sum1[l] += s;
    sum1[r + 1] -= e;
    sum2[l + 1] += d;
    sum2[r + 1] -= d;
  }
  for (int i = 1; i <= n; i ++) {
    sum2[i] += sum2[i - 1];
  }
  for (int i = 1; i <= n; i ++) {
    sum1[i] += sum2[i];
  }
  for (int i = 1; i <= n; i ++) {
    sum1[i] += sum1[i - 1];
    ans ^= sum1[i];
  }
  writeln(ans);
  return 0;  
}
最后修改:2019 年 08 月 24 日 08 : 54 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论