初回のOnsite比赛

比较失败

一题未出

旅游也没怎么旅游 比赛也只有cu

但是第一次去了西北（马上又要去），第一次坐这么长途的火车

image-20210507142819158

F. Rooks

LYF签到

平面上双方都有有好多个给定位置的国际象棋rook(城堡，车)，问有多少个下一步就能被吃掉

L. Square

LYF&WD

数学 思维题+简单dp？

A. Namomo Subsequence

LYF&WD

DP

*K. Allin

德州扑克

可能写挂了

补G. Prof. Pang’s sequence

赛场上盯着这道题毫无思路，只是觉得肯定要用数据结构

最近(2021.9)研究了一些线段树相关，就把这道题补了补

题意：

给定5e5的数列，5e5个询问，问区间内有多少子区间的不同的数的个数是奇数个。

解：

首先需要了解线段树的一种用法：维护历史版本和

意思就是对于每个节点，存一个last表示上次更新的时间。利用这个last算出到现在的时间，再利用其它存下来的值就计算出现在时刻当前节点的答案。

这道题中，将询问离线之后，按顺序将第i个位置造成的贡献加入线段树。设当前时间nowt=这里的i。

可以发现，当加入了a[i]后，以las[a[i]]-a[i]开始到当前i结束的区间的奇偶都翻转了

把这些信息都维护好就行了，细节很多 还有关于何时pushdown的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
//by Richard
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
using namespace std;
mt19937 rnd(19260817);
const int inf=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int> pii;
///////////////////////read5.1///////////////////////
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
////////////////variables&functions//////////////////
const int maxn=555555;
int n,a[maxn],m,last[maxn],nowt;
LL ans[maxn];
struct Query
{
    int l,r,id;
    bool operator<(const Query &b)const
    {
        if (r==b.r) return l<b.l;
        return r<b.r;
    }
}q[maxn];
struct SEG
{
    struct Node
	{
        int last,tm[2],num[2];//last: when change this node; tm:how long has it ; num: how many
        LL ans;
        bool tag;
    }data[maxn<<2];
    void pushdown(int n,bool flag)
	{
        data[n].tm[data[n].tag]+=nowt-data[n].last;
        data[n].last=nowt;
        data[n].ans+=(LL)data[n].num[1]*data[n].tm[0]+(LL)data[n].num[0]*data[n].tm[1];
        if (!flag)
        {
            bool ll=data[n<<1].tag,rr=data[n<<1|1].tag;
            rep(i,0,1) 
            {
                data[n<<1].tm[ll^i]+=data[n].tm[i];
                data[n<<1|1].tm[rr^i]+=data[n].tm[i];
            }
            data[n<<1].tag^=data[n].tag;
            data[n<<1|1].tag^=data[n].tag;
            data[n<<1].last=data[n<<1|1].last=nowt;
        }
        if (data[n].tag) swap(data[n].num[0],data[n].num[1]);
        data[n].tag=0;
        data[n].tm[0]=data[n].tm[1]=0;
    }
    void pushup(int n)
	{
        data[n].num[0]=data[n<<1].num[0]+data[n<<1|1].num[0];
        data[n].num[1]=data[n<<1].num[1]+data[n<<1|1].num[1];
        data[n].ans=data[n<<1].ans+data[n<<1|1].ans;
    }
    void change(int n,int L,int R,int l,int r)
	{
        if (L==l&&R==r)
        {
            nowt--;
            pushdown(n,L==R);
            nowt++;
            data[n].tag=1;
            pushdown(n,L==R);
            return;
        }
        pushdown(n,L==R);
        int mid=(L+R)>>1;
        if (L!=R) {pushdown(n<<1,L==mid);pushdown(n<<1|1,mid+1==R);}
        if (r<=mid) change(n<<1,L,mid,l,r);
        else if (l>mid) change(n<<1|1,mid+1,R,l,r);
        else {change(n<<1,L,mid,l,mid);change(n<<1|1,mid+1,R,mid+1,r);}
        pushup(n);
    }
    LL query(int n,int L,int R,int l,int r)
	{
        pushdown(n,L==R);
        if (L==l&&R==r) return data[n].ans;
        int mid=(L+R)>>1;
        if (r<=mid) return query(n<<1,L,mid,l,r);
        else if (l>mid) return query(n<<1|1,mid+1,R,l,r);
        else return query(n<<1,L,mid,l,mid)+query(n<<1|1,mid+1,R,mid+1,r);
    }
    int build(int n,int L,int R)
	{
        if (L==R) return data[n].num[0]=1;
        int mid=(L+R)>>1;
        return data[n].num[0]=build(n<<1,L,mid)+build(n<<1|1,mid+1,R);
    }
}seg;
int main()
{
    read(n);
    seg.build(1,1,n);
    rep(i,1,n) read(a[i]);
    read(m);
    rep(i,1,m) {read(q[i].l,q[i].r);q[i].id=i;}
    sort(q+1,q+m+1);
    nowt=0;
    rep(i,1,m)
    {
        while (nowt<q[i].r)
        {
            nowt++;
            seg.change(1,1,n,last[a[nowt]]+1,nowt);
            last[a[nowt]]=nowt;
        }
        ans[q[i].id]=seg.query(1,1,n,q[i].l,q[i].r);
    }
    rep(i,1,m) printf("%lld\n",ans[i]);
    return 0;
}