• 欢迎光临~

P4231 三步必杀——二阶差分

问题摘要：

(N)个柱子排成一排，一开始每个柱子损伤度为0。

输出格式

（异或和就是所有数字按位异或起来的值）

（异或运算符在c++里为^）

样例 #1

样例输入 #1

``````5 2
1 5 2 10
2 4 1 1
``````

样例输出 #1

``````3 10
``````

样例 #2

样例输入 #2

``````6 2
1 5 2 10
2 4 1 1
``````

样例输出 #2

``````3 10
``````

提示

数据范围：

(b_L = b_L + s)

(b_{x}=b_x+d)

(b_{R+1}=b_{R+1}-t)

(c_L=c_L+s)

(c_{L+1}=c_{L+1}+d-s)

(c_{x}=c_x)

(c_{R+1}=C_{R+1}-t-d)

(c_{R+2}=c_{R+2}+t)

``````#include <bits/stdc++.h>
#define rei register int
#define ll long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i, s, n, c) for (register int i = s; i <= n; i+=c)
#define repd(i, s, n, c) for (register int i = s; i >= n; i-=c)
#define CHECK cout<<"WALKED"<<endl;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
#define pb push_back
#define ls id<<1
#define rs id<<1|1
const int INF = INT_MAX;
long long binpow(long long a, long long b, ll mod){long long res = 1;  while (b > 0){if (b & 1) res = res * a % mod;a = a * a % mod;  b >>= 1;  }  return res;}

using namespace std;

const int maxn = 10000005;

ll a[maxn], b[maxn], c[maxn], maxx, sum;
int n, m;
int l, r, s, e, d;

int main()
{
for (int i = 1; i <= m; i++) {
d = (e - s) / (r - l); // get common difference

// 4 places
c[l] = c[l] + s;
c[l + 1] = c[l + 1] + d - s;
c[r + 1] = c[r + 1] - d - e;
c[r + 2] = c[r + 2] + e;
}
for (int i = 1; i <= n; i++) {
b[i] = b[i - 1] + c[i]; // second diff
a[i] = a[i - 1] + b[i]; // first diff
}
for (int i = 1; i <= n; i++) {
maxx = max(a[i], maxx);
sum ^= a[i];
}
cout << sum << " " << maxx << endl;
return 0;
}
``````