190052025-11-15 20:55:31gortomiPáros részgráfokcpp17Accepted 100/1001.171s21268 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
int n, m;
int wr = 0;
int tr = 0;
vector<pii> v;
vector<int> p;
vector<int> s;
int get(int v)
{
    return p[v] == 0 ? v : get(p[v]);
}
void unio(int a, int b)
{
    a = get(a);
    b = get(b);
    if(a != b)
    {
        if(s[a] < s[b]) swap(a, b);
        v.push_back({b, a});
        p[b] = a;
        s[a] += s[b];
    }
    else
    {
        v.push_back({0, 0});
    }
}
void edge(pair<int, int> a)
{
    //tr++;
    unio(a.fi, a.se + n);
    unio(a.fi + n, a.se);
    if(get(a.fi + n) == get(a.fi))
    {
        wr++;
        v.push_back({-1, 0});
    }
}
void rollback()
{
    //tr--;
    for(int i = 0; i < 2; i++)
    {
        while(v.back().fi == -1)
        {
            v.pop_back();
            wr--;
        }
        auto [b, a] = v.back();
        v.pop_back();
        s[a] -= s[b];
        p[b] = 0;
    }
}
int l, r;
const int e = 20;
int bmax = -1;
vector<pair<int, int> > fr(e, {0, -1}), ba(e, {0, -1});
vector<pair<int, int> > a;
void ad()
{
    int siz = 0;
    while(fr[siz].fi != 0) siz++;
    int w = (1 << siz) - 1;
    for(int i = 0; i <= siz; i++)
    {
        fr[i] = {0, -1};
        if(ba[i].fi != 0) w += (1 << i);
    }

    for(int i = 0; i < w; i++)
    {
        rollback();
    }

    if(bmax < siz)
    {
        ba[siz] = {r - (1 << siz) + 1, r};
        bmax = siz;
    }
    else fr[siz] = {r - (1 << siz) + 1, r};

    for(int i = siz; i >= 0; i--)
    {
        for(int j = fr[i].fi; j <= fr[i].se; j++)
        {
            edge(a[j]);
        }
        for(int j = ba[i].fi; j <= ba[i].se; j++)
        {
            edge(a[j]);
        }
    }
}
void rem()
{
    int siz = 0;
    while(ba[siz].fi == 0) siz++;
    int w = 0;
    for(int i = 0; i < siz; i++)
    {
        if(fr[i].fi != 0) w += (1 << i);
        ba[i] = {l + (1 << i) - 1, l + (1 << (i + 1)) - 2};
    }
    w += (1 << siz);
    //cout << w << " " << tr << endl;
    for(int i = 0; i < w; i++) rollback();
    ba[siz] = {0, -1};
    if(bmax == siz)
    {
        if(fr[siz].fi != 0)
        {
            ba[siz] = fr[siz];
            fr[siz] = {0, -1};
        }
        else bmax--;
    }
    for(int i = siz - 1; i >= 0; i--)
    {
        for(int j = fr[i].fi; j <= fr[i].se; j++)
        {
            edge(a[j]);
        }
        for(int j = ba[i].fi; j <= ba[i].se; j++)
        {
            edge(a[j]);
        }
    }
}
void solve()
{
    cin >> n >> m;
    p.resize(2 * n + 1);
    s.resize(2 * n + 1, 1);
    a.resize(m + 1);
    for(int i = 1; i <= m; i++)
    {
        cin >> a[i].fi >> a[i].se;
    }
    l = 1;
    int ans = 0;
    for(r = 1; r <= m; r++)
    {
        ad();

        /*
        cout << r << " " << tr << endl;
        for(int j = 0; j < e; j++)
        {
            if(fr[j].fi != 0) cout << fr[j].fi << " . " << fr[j].se << endl;
            if(ba[j].fi != 0) cout << ba[j].fi << " x " << ba[j].se << endl;
        }
        */

        while(wr > 0)
        {
            l++;
            rem();
            //cout << l << endl;
            //cout << "ok" << endl;
        }
        ans += r - l + 1;
        //cout << l << " " << r << endl;
    }
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int te = 1;
    //cin >> te;
    while(te--) solve();
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask210/10
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
subtask37/7
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Accepted1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms316 KiB
22Accepted1ms316 KiB
23Accepted1ms508 KiB
24Accepted1ms316 KiB
25Accepted1ms316 KiB
26Accepted1ms316 KiB
27Accepted1ms316 KiB
28Accepted1ms316 KiB
29Accepted1ms508 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms500 KiB
subtask410/10
33Accepted1ms316 KiB
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
39Accepted1ms316 KiB
40Accepted1ms316 KiB
41Accepted1ms316 KiB
42Accepted1ms316 KiB
43Accepted1ms508 KiB
44Accepted1ms316 KiB
45Accepted1ms316 KiB
46Accepted1ms316 KiB
47Accepted1ms316 KiB
48Accepted1ms316 KiB
49Accepted1ms508 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms500 KiB
53Accepted2ms520 KiB
54Accepted2ms316 KiB
55Accepted1ms316 KiB
56Accepted2ms316 KiB
57Accepted2ms316 KiB
58Accepted2ms316 KiB
59Accepted2ms316 KiB
60Accepted2ms540 KiB
61Accepted1ms316 KiB
62Accepted1ms316 KiB
subtask520/20
63Accepted1ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
67Accepted1ms316 KiB
68Accepted1ms316 KiB
69Accepted1ms316 KiB
70Accepted1ms316 KiB
71Accepted1ms316 KiB
72Accepted1ms316 KiB
73Accepted1ms508 KiB
74Accepted1ms316 KiB
75Accepted1ms316 KiB
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms508 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms500 KiB
83Accepted2ms520 KiB
84Accepted2ms316 KiB
85Accepted1ms316 KiB
86Accepted2ms316 KiB
87Accepted2ms316 KiB
88Accepted2ms316 KiB
89Accepted2ms316 KiB
90Accepted2ms540 KiB
91Accepted1ms316 KiB
92Accepted1ms316 KiB
93Accepted32ms1920 KiB
94Accepted45ms2444 KiB
95Accepted13ms1604 KiB
96Accepted46ms2440 KiB
97Accepted12ms1844 KiB
98Accepted37ms2944 KiB
99Accepted32ms2792 KiB
100Accepted32ms2992 KiB
101Accepted32ms2028 KiB
102Accepted39ms2804 KiB
subtask614/14
103Accepted1ms316 KiB
104Accepted1ms316 KiB
105Accepted1ms316 KiB
106Accepted1ms316 KiB
107Accepted1ms316 KiB
108Accepted1ms316 KiB
109Accepted1ms316 KiB
110Accepted1ms316 KiB
111Accepted1ms316 KiB
112Accepted1ms316 KiB
113Accepted1ms508 KiB
114Accepted1ms316 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Accepted1ms316 KiB
118Accepted1ms316 KiB
119Accepted1ms508 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Accepted1ms500 KiB
123Accepted2ms520 KiB
124Accepted2ms316 KiB
125Accepted1ms316 KiB
126Accepted2ms316 KiB
127Accepted2ms316 KiB
128Accepted2ms316 KiB
129Accepted2ms316 KiB
130Accepted2ms540 KiB
131Accepted1ms316 KiB
132Accepted1ms316 KiB
133Accepted32ms1920 KiB
134Accepted45ms2444 KiB
135Accepted13ms1604 KiB
136Accepted46ms2440 KiB
137Accepted12ms1844 KiB
138Accepted37ms2944 KiB
139Accepted32ms2792 KiB
140Accepted32ms2992 KiB
141Accepted32ms2028 KiB
142Accepted39ms2804 KiB
143Accepted68ms3468 KiB
144Accepted68ms5292 KiB
145Accepted75ms5292 KiB
146Accepted68ms3256 KiB
147Accepted24ms3132 KiB
148Accepted98ms4256 KiB
149Accepted90ms5428 KiB
150Accepted76ms5328 KiB
151Accepted101ms4272 KiB
152Accepted68ms3664 KiB
subtask720/20
153Accepted1ms316 KiB
154Accepted1ms316 KiB
155Accepted1ms316 KiB
156Accepted1ms316 KiB
157Accepted1ms316 KiB
158Accepted1ms316 KiB
159Accepted1ms316 KiB
160Accepted1ms316 KiB
161Accepted1ms316 KiB
162Accepted1ms316 KiB
163Accepted1ms508 KiB
164Accepted1ms316 KiB
165Accepted1ms316 KiB
166Accepted1ms316 KiB
167Accepted1ms316 KiB
168Accepted1ms316 KiB
169Accepted1ms508 KiB
170Accepted1ms316 KiB
171Accepted1ms316 KiB
172Accepted1ms500 KiB
173Accepted2ms520 KiB
174Accepted2ms316 KiB
175Accepted1ms316 KiB
176Accepted2ms316 KiB
177Accepted2ms316 KiB
178Accepted2ms316 KiB
179Accepted2ms316 KiB
180Accepted2ms540 KiB
181Accepted1ms316 KiB
182Accepted1ms316 KiB
183Accepted32ms1920 KiB
184Accepted45ms2444 KiB
185Accepted13ms1604 KiB
186Accepted46ms2440 KiB
187Accepted12ms1844 KiB
188Accepted37ms2944 KiB
189Accepted32ms2792 KiB
190Accepted32ms2992 KiB
191Accepted32ms2028 KiB
192Accepted39ms2804 KiB
193Accepted68ms3468 KiB
194Accepted68ms5292 KiB
195Accepted75ms5292 KiB
196Accepted68ms3256 KiB
197Accepted24ms3132 KiB
198Accepted98ms4256 KiB
199Accepted90ms5428 KiB
200Accepted76ms5328 KiB
201Accepted101ms4272 KiB
202Accepted68ms3664 KiB
203Accepted119ms5548 KiB
204Accepted119ms9128 KiB
205Accepted144ms9344 KiB
206Accepted119ms5544 KiB
207Accepted37ms4916 KiB
208Accepted185ms7084 KiB
209Accepted192ms9128 KiB
210Accepted158ms9356 KiB
211Accepted200ms7084 KiB
212Accepted122ms5548 KiB
subtask819/19
213Accepted1ms500 KiB
214Accepted1ms316 KiB
215Accepted1ms316 KiB
216Accepted1ms316 KiB
217Accepted1ms316 KiB
218Accepted1ms316 KiB
219Accepted1ms316 KiB
220Accepted1ms316 KiB
221Accepted1ms316 KiB
222Accepted1ms316 KiB
223Accepted1ms316 KiB
224Accepted1ms316 KiB
225Accepted1ms508 KiB
226Accepted1ms316 KiB
227Accepted1ms316 KiB
228Accepted1ms316 KiB
229Accepted1ms316 KiB
230Accepted1ms316 KiB
231Accepted1ms508 KiB
232Accepted1ms316 KiB
233Accepted1ms316 KiB
234Accepted1ms500 KiB
235Accepted2ms520 KiB
236Accepted2ms316 KiB
237Accepted1ms316 KiB
238Accepted2ms316 KiB
239Accepted2ms316 KiB
240Accepted2ms316 KiB
241Accepted2ms316 KiB
242Accepted2ms540 KiB
243Accepted1ms316 KiB
244Accepted1ms316 KiB
245Accepted32ms1920 KiB
246Accepted45ms2444 KiB
247Accepted13ms1604 KiB
248Accepted46ms2440 KiB
249Accepted12ms1844 KiB
250Accepted37ms2944 KiB
251Accepted32ms2792 KiB
252Accepted32ms2992 KiB
253Accepted32ms2028 KiB
254Accepted39ms2804 KiB
255Accepted68ms3468 KiB
256Accepted68ms5292 KiB
257Accepted75ms5292 KiB
258Accepted68ms3256 KiB
259Accepted24ms3132 KiB
260Accepted98ms4256 KiB
261Accepted90ms5428 KiB
262Accepted76ms5328 KiB
263Accepted101ms4272 KiB
264Accepted68ms3664 KiB
265Accepted119ms5548 KiB
266Accepted119ms9128 KiB
267Accepted144ms9344 KiB
268Accepted119ms5544 KiB
269Accepted37ms4916 KiB
270Accepted185ms7084 KiB
271Accepted192ms9128 KiB
272Accepted158ms9356 KiB
273Accepted200ms7084 KiB
274Accepted122ms5548 KiB
275Accepted541ms21152 KiB
276Accepted926ms21156 KiB
277Accepted541ms21268 KiB
278Accepted926ms21268 KiB
279Accepted1.171s17064 KiB
280Accepted620ms17064 KiB
281Accepted907ms21264 KiB
282Accepted925ms21124 KiB
283Accepted795ms21152 KiB
284Accepted542ms21152 KiB