8.7考试总结

· · 个人记录

T1

发现如果 r_i-l_i+1<i，只可能有一个。

所以对于每个站点，找有多少个是他的倍数的个数。

最后把 r_i-l_i+1\ge i 的 n-j+1 个加上即可。

//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

对于现在在的 i，如果是 1 操作，那么之后还需修改 m - i 次。

如果需要在 j 查询，则还需修改 m-j 次。

建立两个线段树，一个计算 x \times (m-i)，一个计算 x。

答案就是两颗线段树减去 m-j 的差即可。

//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

~洛谷数据好水！！！~

用一些奇奇怪怪的分块，看老师最后没讲。