190062025-11-15 21:02:19gortomiPáros részgráfokcpp17Accepted 100/100953ms10928 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;
    ll 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
23Accepted1ms368 KiB
24Accepted1ms316 KiB
25Accepted1ms316 KiB
26Accepted1ms316 KiB
27Accepted1ms316 KiB
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
subtask410/10
33Accepted1ms316 KiB
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
39Accepted1ms316 KiB
40Accepted1ms316 KiB
41Accepted1ms316 KiB
42Accepted1ms316 KiB
43Accepted1ms368 KiB
44Accepted1ms316 KiB
45Accepted1ms316 KiB
46Accepted1ms316 KiB
47Accepted1ms316 KiB
48Accepted1ms316 KiB
49Accepted1ms316 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms316 KiB
53Accepted2ms500 KiB
54Accepted2ms316 KiB
55Accepted1ms316 KiB
56Accepted2ms316 KiB
57Accepted2ms316 KiB
58Accepted2ms316 KiB
59Accepted2ms316 KiB
60Accepted1ms316 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
73Accepted1ms368 KiB
74Accepted1ms316 KiB
75Accepted1ms316 KiB
76Accepted1ms316 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted2ms500 KiB
84Accepted2ms316 KiB
85Accepted1ms316 KiB
86Accepted2ms316 KiB
87Accepted2ms316 KiB
88Accepted2ms316 KiB
89Accepted2ms316 KiB
90Accepted1ms316 KiB
91Accepted1ms316 KiB
92Accepted1ms316 KiB
93Accepted32ms1160 KiB
94Accepted41ms1508 KiB
95Accepted12ms1088 KiB
96Accepted43ms1480 KiB
97Accepted12ms1080 KiB
98Accepted37ms1696 KiB
99Accepted35ms1676 KiB
100Accepted32ms1784 KiB
101Accepted32ms1200 KiB
102Accepted39ms1712 KiB
subtask614/14
103Accepted1ms316 KiB
104Accepted1ms316 KiB
105Accepted1ms316 KiB
106Accepted1ms316 KiB
107Accepted1ms316 KiB
108Accepted1ms316 KiB
109Accepted1ms316 KiB
110Accepted1ms316 KiB
111Accepted1ms316 KiB
112Accepted1ms316 KiB
113Accepted1ms368 KiB
114Accepted1ms316 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Accepted1ms316 KiB
118Accepted1ms316 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Accepted1ms316 KiB
123Accepted2ms500 KiB
124Accepted2ms316 KiB
125Accepted1ms316 KiB
126Accepted2ms316 KiB
127Accepted2ms316 KiB
128Accepted2ms316 KiB
129Accepted2ms316 KiB
130Accepted1ms316 KiB
131Accepted1ms316 KiB
132Accepted1ms316 KiB
133Accepted32ms1160 KiB
134Accepted41ms1508 KiB
135Accepted12ms1088 KiB
136Accepted43ms1480 KiB
137Accepted12ms1080 KiB
138Accepted37ms1696 KiB
139Accepted35ms1676 KiB
140Accepted32ms1784 KiB
141Accepted32ms1200 KiB
142Accepted39ms1712 KiB
143Accepted70ms1880 KiB
144Accepted68ms2772 KiB
145Accepted72ms2996 KiB
146Accepted70ms1972 KiB
147Accepted24ms1844 KiB
148Accepted92ms2476 KiB
149Accepted85ms2996 KiB
150Accepted74ms3008 KiB
151Accepted93ms2484 KiB
152Accepted71ms1988 KiB
subtask720/20
153Accepted1ms316 KiB
154Accepted1ms316 KiB
155Accepted1ms316 KiB
156Accepted1ms316 KiB
157Accepted1ms316 KiB
158Accepted1ms316 KiB
159Accepted1ms316 KiB
160Accepted1ms316 KiB
161Accepted1ms316 KiB
162Accepted1ms316 KiB
163Accepted1ms368 KiB
164Accepted1ms316 KiB
165Accepted1ms316 KiB
166Accepted1ms316 KiB
167Accepted1ms316 KiB
168Accepted1ms316 KiB
169Accepted1ms316 KiB
170Accepted1ms316 KiB
171Accepted1ms316 KiB
172Accepted1ms316 KiB
173Accepted2ms500 KiB
174Accepted2ms316 KiB
175Accepted1ms316 KiB
176Accepted2ms316 KiB
177Accepted2ms316 KiB
178Accepted2ms316 KiB
179Accepted2ms316 KiB
180Accepted1ms316 KiB
181Accepted1ms316 KiB
182Accepted1ms316 KiB
183Accepted32ms1160 KiB
184Accepted41ms1508 KiB
185Accepted12ms1088 KiB
186Accepted43ms1480 KiB
187Accepted12ms1080 KiB
188Accepted37ms1696 KiB
189Accepted35ms1676 KiB
190Accepted32ms1784 KiB
191Accepted32ms1200 KiB
192Accepted39ms1712 KiB
193Accepted70ms1880 KiB
194Accepted68ms2772 KiB
195Accepted72ms2996 KiB
196Accepted70ms1972 KiB
197Accepted24ms1844 KiB
198Accepted92ms2476 KiB
199Accepted85ms2996 KiB
200Accepted74ms3008 KiB
201Accepted93ms2484 KiB
202Accepted71ms1988 KiB
203Accepted122ms3108 KiB
204Accepted119ms4968 KiB
205Accepted136ms4780 KiB
206Accepted122ms2992 KiB
207Accepted39ms2808 KiB
208Accepted170ms3752 KiB
209Accepted172ms4960 KiB
210Accepted146ms4960 KiB
211Accepted185ms3940 KiB
212Accepted123ms2992 KiB
subtask819/19
213Accepted1ms316 KiB
214Accepted1ms500 KiB
215Accepted1ms316 KiB
216Accepted1ms316 KiB
217Accepted1ms316 KiB
218Accepted1ms316 KiB
219Accepted1ms316 KiB
220Accepted1ms316 KiB
221Accepted1ms316 KiB
222Accepted1ms316 KiB
223Accepted1ms316 KiB
224Accepted1ms316 KiB
225Accepted1ms368 KiB
226Accepted1ms316 KiB
227Accepted1ms316 KiB
228Accepted1ms316 KiB
229Accepted1ms316 KiB
230Accepted1ms316 KiB
231Accepted1ms316 KiB
232Accepted1ms316 KiB
233Accepted1ms316 KiB
234Accepted1ms316 KiB
235Accepted2ms500 KiB
236Accepted2ms316 KiB
237Accepted1ms316 KiB
238Accepted2ms316 KiB
239Accepted2ms316 KiB
240Accepted2ms316 KiB
241Accepted2ms316 KiB
242Accepted1ms316 KiB
243Accepted1ms316 KiB
244Accepted1ms316 KiB
245Accepted32ms1160 KiB
246Accepted41ms1508 KiB
247Accepted12ms1088 KiB
248Accepted43ms1480 KiB
249Accepted12ms1080 KiB
250Accepted37ms1696 KiB
251Accepted35ms1676 KiB
252Accepted32ms1784 KiB
253Accepted32ms1200 KiB
254Accepted39ms1712 KiB
255Accepted70ms1880 KiB
256Accepted68ms2772 KiB
257Accepted72ms2996 KiB
258Accepted70ms1972 KiB
259Accepted24ms1844 KiB
260Accepted92ms2476 KiB
261Accepted85ms2996 KiB
262Accepted74ms3008 KiB
263Accepted93ms2484 KiB
264Accepted71ms1988 KiB
265Accepted122ms3108 KiB
266Accepted119ms4968 KiB
267Accepted136ms4780 KiB
268Accepted122ms2992 KiB
269Accepted39ms2808 KiB
270Accepted170ms3752 KiB
271Accepted172ms4960 KiB
272Accepted146ms4960 KiB
273Accepted185ms3940 KiB
274Accepted123ms2992 KiB
275Accepted549ms10912 KiB
276Accepted790ms10920 KiB
277Accepted546ms10928 KiB
278Accepted792ms10908 KiB
279Accepted953ms8876 KiB
280Accepted485ms8792 KiB
281Accepted782ms10920 KiB
282Accepted791ms10916 KiB
283Accepted714ms10916 KiB
284Accepted544ms10920 KiB