Day5 I sorting

第一行三个整数n, q, x ( 1\leq n, q \leq 2*10^5, 0\leq x\leq 10^9)n,q,x(1≤n,q≤2∗105,0≤x≤109)表示元素的个数和询问的个数。

接下来一行nn个整数a_1, a_2, \dots, a_n(1\leq a_i\leq 10^9)a1​,a2​,…,an​(1≤ai​≤109)。

接下来qq行，每行三个正整数p, l, r (1\leq p\leq 3), 1\leq l\leq r\leq np,l,r(1≤p≤3),1≤l≤r≤n表示操作种类和区间。

对于每个第一种操作，输出一行，表示答案。

赛后补题一发AC，超级开心！！！

Code:

/*
 * 2019年1月25日
 * 题意 ： 要求⽀持区间操作和区间求和
 * 
 * 容易发现<=x的数字和>x的数字的相对顺序不会变。
 * 把<=x的数字当成0，>x的数字当成1。
 * 操作就是区间求和和区间赋值。
 * 区间求和就相当于搞出这是第⼏个0到第⼏个0，第⼏个1到第⼏个1，然后前缀和即可。
 * 区间赋值就相当于将前几个值变为0/1，将后面几个值变为1/0
 * 
 * 各函数作用
 * update ： 区间赋值
 * shunxu :  前面出现了多少次0/1
 * query  ： 当前区间内有多少个0/1
 * 
 * 各数组
 * temp1  ：  <=x的数的前缀和
 * temp2  ：  >x的数的前缀和
 */
#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
struct node
{
	int l;
	int r;
	ll mark;//set
	int zero;
	int one;
}que[200005 * 4];
ll val, a[200005], temp1[200005], temp2[200005], x;
int ql, qr, pre_0, pre_1, cnt_0, cnt_1, n, q;
void up(int k)
{
	que[k].zero = que[k << 1].zero + que[k << 1 | 1].zero;
	que[k].one = que[k << 1].one + que[k << 1 | 1].one;
}
void down(int k)
{
	if (que[k].mark != -1)
	{
		que[k << 1].mark = que[k].mark;
		que[k << 1 | 1].mark = que[k].mark;

		que[k << 1].one = (que[k << 1].r - que[k << 1].l + 1) * que[k].mark;
		que[k << 1].zero = (que[k << 1].r - que[k << 1].l + 1) * (1 - que[k].mark);
		que[k << 1 | 1].one = (que[k << 1 | 1].r - que[k << 1 | 1].l + 1) * que[k].mark;
		que[k << 1 | 1].zero = (que[k << 1 | 1].r - que[k << 1 | 1].l + 1) * (1 - que[k].mark);

		que[k].mark = -1;
	}
}
void build(int left, int right, int k)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = -1;
	if (left == right)
	{
		if (a[left] == 0)
		{
			que[k].zero = 1;
			que[k].one = 0;
		}
		else
		{
			que[k].one = 1;
			que[k].zero = 0;
		}
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
//区间更新
void update(int left, int right, int k)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].mark = val;
		que[k].one = (que[k].r - que[k].l + 1)*val;
		que[k].zero = (que[k].r - que[k].l + 1)*(1 - val);
		return;
	}
	down(k);
	imid;
	update(lson);
	update(rson);
	up(k);
}
//区间第一个0/1出现的位置 pre_0 pre_1表示位置  
//预设值 pre_0,pre_1 置0
//调用shunxu(1, n, 1, 0, 0);后
//全局变量pre_0,pre_1就是之前0/1的次数
void shunxu(int left, int right, int k, int pre0, int pre1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		pre_0 = min(pre_0, pre0);
		pre_1 = min(pre_1, pre1);
		return;
	}
	down(k);
	imid;
	shunxu(lson, pre0, pre1);
	pre0 += que[k << 1].zero;
	pre1 += que[k << 1].one;
	shunxu(rson, pre0, pre1);
}
//区间0/1个数 cnt_0,cnt_1表示个数
//cnt_0,cnt_1 置0
//调用query(1, n, 1);后
//cnt_0,cnt_1就是区间内0/1的次数
void query(int left, int right, int k)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		cnt_0 += que[k].zero;
		cnt_1 += que[k].one;
		return;
	}
	down(k);
	imid;
	query(lson);
	query(rson);
}
int main()
{
	int op, x1 = 1, x2 = 1, qls, qrs;
	scanf("%d%d%lld", &n, &q, &x);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		if (a[i] <= x)
		{
			temp1[x1] = a[i];
			temp1[x1] += temp1[x1 - 1];
			x1++;
			a[i] = 0;
		}
		else
		{
			temp2[x2] = a[i];
			temp2[x2] += temp2[x2 - 1];
			x2++;
			a[i] = 1;
		}
	}
	build(1, n, 1);
	while (q--)
	{
		scanf("%d%d%d", &op, &qls, &qrs);

		ql = qls;
		qr = qrs;

		//第一次出现的位置
		pre_0 = 200005;
		pre_1 = 200005;
		shunxu(1, n, 1, 0, 0);
		//printf("%d %d\n", pre_0, pre_1);

		//区间内0/1的个数
		cnt_0 = 0;
		cnt_1 = 0;
		query(1, n, 1);
		//printf("%d %d\n", cnt_0, cnt_1);
		
		if (op == 1)
		{
			printf("%lld\n", temp1[pre_0 + cnt_0] - temp1[pre_0] + temp2[pre_1 + cnt_1] - temp2[pre_1]);
		}
		else if (op == 2)
		{
			ql = qls;
			qr = qls + cnt_0 - 1;
			val = 0;
			update(1, n, 1);
			ql = qls + cnt_0;
			qr = qrs;
			val = 1;
			update(1, n, 1);
		}
		else
		{
			ql = qls;
			qr = qls + cnt_1 - 1;
			val = 1;
			update(1, n, 1);
			ql = qls + cnt_1;
			qr = qrs;
			val = 0;
			update(1, n, 1);
		}
	}
}

Code2：

#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
struct node
{
	int l;
	int r;
	ll mark;
	int zero;//sum
	int one;
}que[200005 * 4];
int n, m, x, a[200005], ql, qr;
ll pre1[200005], pre2[200005];//小于x的是pre1，大于x的是pre2
int cnt1 = 1, cnt2 = 1;
ll val;
void up(int k)
{
	que[k].zero = que[k << 1].zero + que[k << 1 | 1].zero;
	que[k].one = que[k << 1].one + que[k << 1 | 1].one;
}
void down(int k)
{
	if (que[k].mark != -1)
	{
		que[k << 1].mark = que[k].mark;
		que[k << 1 | 1].mark = que[k].mark;

		if (que[k].mark == 0)
		{
			que[k << 1].zero = que[k << 1].r - que[k << 1].l + 1;
			que[k << 1 | 1].zero = que[k << 1 | 1].r - que[k << 1 | 1].l + 1;
			que[k << 1].one = 0;
			que[k << 1 | 1].one = 0;
		}
		else
		{
			que[k << 1].zero = 0;
			que[k << 1 | 1].zero = 0;
			que[k << 1].one = que[k << 1].r - que[k << 1].l + 1;
			que[k << 1 | 1].one = que[k << 1 | 1].r - que[k << 1 | 1].l + 1;
		}

		que[k].mark = -1;
	}
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = -1;
	if (left == right)
	{
		if (a[left] <= x)
			que[k].zero++;
		else
			que[k].one++;
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
void update(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].mark = val;
		if (val == 0)
		{
			que[k].zero = que[k].r - que[k].l + 1;
			que[k].one = 0;
		}
		else
		{
			que[k].zero = 0;
			que[k].one = que[k].r - que[k].l + 1;
		}
		return;
	}
	down(k);
	imid;
	update(lson);
	update(rson);
	up(k);
}
//区间ql-qr中 0 的个数
int query_zero(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].zero;
	down(k);
	imid;
	return query_zero(lson) + query_zero(rson);
}
//区间ql-qr中 1 的个数
int query_one(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].one;
	down(k);
	imid;
	return query_one(lson) + query_one(rson);
}
int main()
{
	scanf("%d%d%d", &n, &m, &x);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		if (a[i] <= x)
			pre1[cnt1++] = a[i];
		else
			pre2[cnt2++] = a[i];
	}
	for (int i = 1; i < cnt1; i++)
		pre1[i] += pre1[i - 1];
	for (int i = 1; i < cnt2; i++)
		pre2[i] += pre2[i - 1];
	build();
	int op, l, r;
	while (m--)
	{
		scanf("%d%d%d", &op, &l, &r);
		//pre1是0，pre2是1
		if (op == 1)
		{
			int q0 = 0, q1 = 0, w0 = 0, w1 = 0;
			if (1 <= r)
			{
				ql = 1;
				qr = r;
				q0 = query_zero();
				q1 = query_one();
			}
			if (1 <= l - 1)
			{
				ql = 1;
				qr = l - 1;
				w0 = query_zero();
				w1 = query_one();
			}
			printf("%lld\n", pre1[q0] - pre1[w0] + pre2[q1] - pre2[w1]);
		}
		else if (op == 2)
		{
			ql = l;
			qr = r;
			int zero = query_zero();
			int one = query_one();
			ql = l;
			qr = l + zero - 1;
			val = 0;
			update();
			ql = l + zero;
			qr = r;
			val = 1;
			update();
		}
		else
		{
			ql = l;
			qr = r;
			int zero = query_zero();
			int one = query_one();
			ql = l;
			qr = l + one - 1;
			val = 1;
			update();
			ql = l + one;
			qr = r;
			val = 0;
			update();
		}
	}
}