专栏文章

8.7考试总结

HHhy140516
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miogtg0y
此快照首次捕获于
2025/12/02 18:58
3 个月前
此快照最后确认于
2025/12/02 18:58
3 个月前
查看原文

T1

发现如果 ri−li+1<ir_i-l_i+1<i，只可能有一个。
所以对于每个站点，找有多少个是他的倍数的个数。
最后把 ri−li+1≥ir_i-l_i+1\ge i 的 n−j+1n-j+1 个加上即可。
CPP
//Code by hhy
#include<bits/stdc++.h>
// #define int long long
#define ull unsigned long long
#define ll long long
using namespace std ;
const int kMaxN = 3e5 + 5 , MOD = 998244353 , INF = 1e18 ;
int n , m ;
int c[kMaxN] ;
struct node
{
	int l , r , len ;
}a[kMaxN] ;
bool cmp(node x , node y)
{
	return x.len < y.len ;
}
int lowbit(int x)
{
	return (x & (-x)) ;
}
void update(int x , int v)
{
	while(x <= m)
	{
		c[x] += v ;
		x += lowbit(x) ;
	}
}
int query(int x)
{
	int sum = 0 ;
	while(x > 0)
	{
	  sum += c[x] ;
		x -= lowbit(x) ;
	}
	return sum ;
}
void work()
{
	cin >> n >> m ;
	for( int i = 1 ; i <= n ; i++ )
	{
		cin >> a[i].l >> a[i].r ;
		a[i].len = a[i].r - a[i].l + 1 ;
	}
	sort(a + 1 , a + n + 1 , cmp) ;
	int j = 1 ;
	for( int i = 1 ; i <= m ; i++ )
	{
		while(j <= n && a[j].len < i)
		{
			update(a[j].l , 1) ;
			update(a[j].r + 1 , -1) ;
			j++ ;
		}
		int sum = 0 ;
		for( int k = i ; k <= m ; k += i )
		{
			sum += query(k) ;
		}
		cout << sum + n - j + 1 << "\n" ;
	}
}
signed main()
{
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

T2

这题就是单调栈模板。
找到左右两边大于这个值的下表，这个值的贡献只可能是在这里产生，直接算贡献。
但是有可能相等，左右两边任意选一边改为大于等于即可。

T3

对于现在在的 ii，如果是 11 操作，那么之后还需修改 m−im - i 次。
如果需要在 jj 查询，则还需修改 m−jm-j 次。
建立两个线段树，一个计算 x×(m−i)x \times (m-i)，一个计算 xx。
答案就是两颗线段树减去 m−jm-j 的差即可。
CPP
//Code by hhy
#include<bits/stdc++.h>
// #define int long long
#define ull unsigned long long
#define ll long long
#define lson(x) (x << 1) 
#define rson(x) ((x << 1) | 1) 
using namespace std ;
const int kMaxN = 1e5 + 5 , MOD = 998244353 , INF = 1e9 ;
int n , m ;
int a[kMaxN] ;
struct node
{
	int t[kMaxN << 2] , lazy[kMaxN << 2] ;
	void push_up(int k)
	{
		t[k] = t[lson(k)] + t[rson(k)] ;
	}
	void update_son(int k , int l , int r , ll v)
	{
		lazy[k] += v ;
		t[k] += (r - l + 1) * v ;
	}
	void push_down(int k , int l , int r)
	{
		if(!lazy[k]) return ;
		int mid = l + r >> 1 ;
		update_son(lson(k) , l , mid , lazy[k]) ;
		update_son(rson(k) , mid + 1 , r , lazy[k]) ;
		lazy[k] = 0 ;
	}
	void build(int k , int l , int r)
	{
		lazy[k] = 0 ;
		if(l == r)
		{
			t[k] = a[l] ;
			return ;
		}
		int mid = l + r >> 1 ;
		build(lson(k) , l , mid) ;
		build(rson(k) , mid + 1 , r) ;
		push_up(k) ;
	}
	void update(int L , int R , int x , int k , int l , int r)
	{
		if(L <= l && r <= R)
		{
	    update_son(k , l , r , x) ;
			return ;
		}
		int mid = l + r >> 1 ;
		push_down(k , l , r) ;
		if(L <= mid)
		{
			update(L , R , x , lson(k) , l , mid) ;
		}
		if(R > mid)
		{
			update(L , R , x , rson(k) , mid + 1 , r) ;
		}
		push_up(k) ;
	}
	int ans(int L , int R , int k , int l , int r)
	{
		if(L <= l && r <= R)
		{
			return t[k] ;
		}
		int res = 0 ;
		int mid = l + r >> 1 ;
		push_down(k , l , r) ;
		if(L <= mid)
		{
			res += ans(L , R , lson(k) , l , mid) ;
		}
		if(R > mid)
		{
			res += ans(L , R , rson(k) , mid + 1 , r) ;
		}
		return res ;
	}
}tr1 , tr2 ;
void work()
{
	cin >> n ;
	for( int i = 1 ; i <= n ; i++ ) 
	{
		cin >> a[i] ;
	}
	cin >> m ;
	tr1.build(1 , 1 , n) ;
	memset(a , 0 , sizeof a) ;
	tr2.build(1 , 1 , n) ;
	for( int i = 1 ; i <= m ; i++ )
	{
		int op , l , r , x ;
		cin >> op >> l >> r ;
		if(op == 1)
		{
			cin >> x ;
			tr1.update(l , r , x * (m - i) , 1 , 1 , n) ;
			tr2.update(l , r , x , 1 , 1 , n) ;
		}
		else
		{
			cout << tr1.ans(l , r , 1 , 1 , n) - tr2.ans(l , r , 1 , 1 , n) * (m - i) << "\n" ; 
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

T4

~洛谷数据好水！！！~
用一些奇奇怪怪的分块，看老师最后没讲。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...